I**A 发帖数: 2345 | 1 MIT 那个 hack google interview 上给的code,是不是有问题?
boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}
boolean isValidHelper(Node curr, int min, int max) {
if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
return true;
} |
f*********5 发帖数: 576 | 2 说说看你觉得有什么问题?
【在 I**A 的大作中提到】 : MIT 那个 hack google interview 上给的code,是不是有问题? : boolean isValid(Node root) { : return isValidHelper(root, Integer.MIN_VALUE, : Integer.MAX_VALUE); : } : boolean isValidHelper(Node curr, int min, int max) { : if (curr.left != null) { : if (curr.left.value < min || : !isValidHelper(curr.left, min, curr.value)) : return false;
|
I**A 发帖数: 2345 | 3 首先,root的value没有被check
再次,在initial min and max 被 replace之前,我感觉也有问题
【在 f*********5 的大作中提到】 : 说说看你觉得有什么问题?
|
I**A 发帖数: 2345 | 4 同学,那可是MIT出的材料哎,要尊重权威~~~
除了这两点呢,有没有我没有看出来的?
上次大家说的要检测node.data要大于min小于max
这个右孩子的min and 和左孩子的max是怎样求的?
【在 f*********5 的大作中提到】 : 说说看你觉得有什么问题?
|
f*********5 发帖数: 576 | 5 if (curr.left != null) {
if (curr.left.value < min ||
!isValidHelper(curr.left, min, curr.value))
return false;
}
if (curr.right != null) {
if (curr.right.value > max ||
!isValidHelper(curr.right, curr.value, max))
return false;
}
权威的code没问题,
首先,对于int型root.value肯定满足范围。
然后看 左孩子的max小于current.value是由第二部分完成的。
如果左孩子的max大,虽然我们没判断,但是在递归调用的时候,
由于我们设定了左子树的最大范围是current.value,
在左子树中,迟早会有curr.right.value > max。
所以。。。
同理,右孩子的min 〉current.value,是由第一部分实现的。
【在 I**A 的大作中提到】 : 同学,那可是MIT出的材料哎,要尊重权威~~~ : 除了这两点呢,有没有我没有看出来的? : 上次大家说的要检测node.data要大于min小于max : 这个右孩子的min and 和左孩子的max是怎样求的?
|
h**6 发帖数: 4160 | 6 有一点问题,没有检查
curr.left.value > max
或者
curr.right.value < min
的情况。
如果左子树的最大值在左节点,或者右子树的最小值在右节点则无法判断。
重新整理了一下程序,未测试,大家看看对不对:
boolean isValidHelper(Node curr, int min, int max)
{
if(curr == NULL) return true;
else return curr.value>=min && cur.value<=max
&& isValidHelper(curr.left, min, curr.value)
&& isValidHelper(curr.right, curr.value, max);
} |
I**A 发帖数: 2345 | 7 逻辑我没看懂。。
这个CODE肯定是有问题的。。
我测试了一下,自己创建了一个BST
(1)修改了ROOT的VALUE让其不是BST,可是返回TRUE
(2)修改了ROOT.LEFT的VALUE让其不是BST, 还是返回TRUE
【在 f*********5 的大作中提到】 : if (curr.left != null) { : if (curr.left.value < min || : !isValidHelper(curr.left, min, curr.value)) : return false; : } : if (curr.right != null) { : if (curr.right.value > max || : !isValidHelper(curr.right, curr.value, max)) : return false; : }
|
I**A 发帖数: 2345 | 8 我觉得这个对整颗树检查node value 在 allowed range内有问题
(root and its left and right child 这仨node肯定是有问题的,没想明白后面的有
没有。。。)
【在 h**6 的大作中提到】 : 有一点问题,没有检查 : curr.left.value > max : 或者 : curr.right.value < min : 的情况。 : 如果左子树的最大值在左节点,或者右子树的最小值在右节点则无法判断。 : 重新整理了一下程序,未测试,大家看看对不对: : boolean isValidHelper(Node curr, int min, int max) : { : if(curr == NULL) return true;
|
f*********5 发帖数: 576 | 9 en,我搞错了,还是需要判断范围。。
【在 I**A 的大作中提到】 : 逻辑我没看懂。。 : 这个CODE肯定是有问题的。。 : 我测试了一下,自己创建了一个BST : (1)修改了ROOT的VALUE让其不是BST,可是返回TRUE : (2)修改了ROOT.LEFT的VALUE让其不是BST, 还是返回TRUE
|
l*********b 发帖数: 1541 | 10 这个太复杂啦。做个inorder, 只要测试每个值比前面大就行啦。 |
|
|
I**A 发帖数: 2345 | 11 再次呼唤一声~~~
你们说的那个max and min到底是怎样求的?
【在 l*********b 的大作中提到】 : 这个太复杂啦。做个inorder, 只要测试每个值比前面大就行啦。
|
l*********b 发帖数: 1541 | |
I**A 发帖数: 2345 | 13 这个我大致看过
int minValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL) {
current = current->left;
}
return(current->data);
}
int maxValue(struct node* node) {
struct node* current = node;
/* loop down to find the leftmost leaf */
while (current->right != NULL) {
current = current->left;
}
return(current->data);
}
这俩function,肯定有一个有问题。。。
再说了,这样求max and min也不make sense,因为只要在保证left or right是BST的
情况下才能
【在 l*********b 的大作中提到】 : http://geeksforgeeks.org/?p=3042
|
l*********b 发帖数: 1541 | 14 我没仔细看。
最好根据自己的理解写一个吧,测试一下,能工作就行。 |
I**A 发帖数: 2345 | 15 我这不就是没想清楚么?
如果按我的想法,那找子树的max and min的时候要check所有的node,可是那样的话,
复杂度蹭就上去了。。
所以想知道大家说的max and min到底是怎么找出来的。。
【在 l*********b 的大作中提到】 : 我没仔细看。 : 最好根据自己的理解写一个吧,测试一下,能工作就行。
|
l*********b 发帖数: 1541 | 16 就是一个递归。
每次递归返回三个值:以该节点为根的子树是否是bst, 子树的最小值和子树的最大值。
找子树的max and min是和check bst同时进行的,复杂度是N。 |
I**A 发帖数: 2345 | 17 不是,我是说怎么找子树的max and min这个问题。。。
值。
【在 l*********b 的大作中提到】 : 就是一个递归。 : 每次递归返回三个值:以该节点为根的子树是否是bst, 子树的最小值和子树的最大值。 : 找子树的max and min是和check bst同时进行的,复杂度是N。
|