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。
|
