K*****k
发帖数: 430 | 1 要求O(1)空间，假定元素都是int，这样写就可以了？
int prev = INT_MIN;
bool IsBST(Node* root)
{
if (root == NULL)
return true;
if (!IsBST(root->left)
return false;
if (prev > root->data)
return false;
prev = root->data;
return IsBST(root->right);
} |
q****x
发帖数: 7404 | 2 how can recursion O(1)? ignoring the stack space?
【在 K*****k 的大作中提到】
: 要求O(1)空间，假定元素都是int，这样写就可以了？
: int prev = INT_MIN;
: bool IsBST(Node* root)
: {
: if (root == NULL)
: return true;
: if (!IsBST(root->left)
: return false;
: if (prev > root->data)
: return false;
|
K*****k
发帖数: 430 | 3 就是不许你递归中序遍历到一个额外的数组，然后判断那个数组是否有序。
不管你用不用递归进行中序遍历，栈空间都是要的。
【在 q****x 的大作中提到】
: how can recursion O(1)? ignoring the stack space?
|
K*****k
发帖数: 430 | 4 好像还有一种方法
bool IsBST(Node* root, int range_min, int range_max);
最初range_min为INT_MIN, range_max为INT_MAX
也是递归，判断当前访问到的节点是否在界内。
但似乎没有上面的解法简洁，直接，明快。 |
b******n
发帖数: 4509 | 5 try
2
/
3
【在 K*****k 的大作中提到】
: 要求O(1)空间，假定元素都是int，这样写就可以了？
: int prev = INT_MIN;
: bool IsBST(Node* root)
: {
: if (root == NULL)
: return true;
: if (!IsBST(root->left)
: return false;
: if (prev > root->data)
: return false;
|
K*****k
发帖数: 430 | 6 对这个test case, 好像木有什么问题，返回false
【在 b******n 的大作中提到】
: try
: 2
: /
: 3
|
a********m
发帖数: 15480 | 7 感觉有问题。那个全局变量应该不是必须的。
【在 K*****k 的大作中提到】
: 要求O(1)空间，假定元素都是int，这样写就可以了？
: int prev = INT_MIN;
: bool IsBST(Node* root)
: {
: if (root == NULL)
: return true;
: if (!IsBST(root->left)
: return false;
: if (prev > root->data)
: return false;
|
K*****k
发帖数: 430 | 8 此外，假定传入的node* root是合法的BT, 不知道这个要不要向interviewer指出？ |
K*****k
发帖数: 430 | 9 不用全局变量，也可以用C++的引用
bool IsBST(node* root, int& prev);
调用前把prev设成INT_MIN
【在 a********m 的大作中提到】
: 感觉有问题。那个全局变量应该不是必须的。
|
S*******0
发帖数: 198 | 10 boolean isBST(Node node, int min, int max) {
if (node == null)
return true;
if (node.data < min || node.data > max)
return false;
return isBST(node.left, min, node.data)
&& isBST(node.right, node.data + 1, max);
}
【在 K*****k 的大作中提到】
: 好像还有一种方法
: bool IsBST(Node* root, int range_min, int range_max);
: 最初range_min为INT_MIN, range_max为INT_MAX
: 也是递归，判断当前访问到的节点是否在界内。
: 但似乎没有上面的解法简洁，直接，明快。
|
|
|
b******n
发帖数: 4509 | 11 应该是对的
【在 K*****k 的大作中提到】
: 对这个test case, 好像木有什么问题，返回false
|
K*****k
发帖数: 430 | 12 node.data + 1是否画蛇添足？
这样下面的BST就被误判为不是了。
1
/ \
1 1
【在 S*******0 的大作中提到】
: boolean isBST(Node node, int min, int max) {
: if (node == null)
: return true;
: if (node.data < min || node.data > max)
: return false;
: return isBST(node.left, min, node.data)
: && isBST(node.right, node.data + 1, max);
: }
|
K*****k
发帖数: 430 | 13 要是面试就考这些常见题应该不难，难的是如果这类题事先没有做过练过，现场要迅速
想出来并写的对。
如果只是看了一下思路觉得我会了，不去实际纸上写写，到时候白板上写可能会忘掉一
些注意事项，或者有考虑不全的地方，或者有笔误和小bug。 |
a********m
发帖数: 15480 | 14 主要是没意义。
判断左右的值和左右两个子树属性就可以了，不需要一个共享的变量，这么做反而增加了代码的复杂程度。
【在 K*****k 的大作中提到】
: 不用全局变量，也可以用C++的引用
: bool IsBST(node* root, int& prev);
: 调用前把prev设成INT_MIN
|
A**u
发帖数: 2458 | 15 max min 更新不
【在 S*******0 的大作中提到】
: boolean isBST(Node node, int min, int max) {
: if (node == null)
: return true;
: if (node.data < min || node.data > max)
: return false;
: return isBST(node.left, min, node.data)
: && isBST(node.right, node.data + 1, max);
: }
|
A**u
发帖数: 2458 | 16 好方法
【在 S*******0 的大作中提到】
: boolean isBST(Node node, int min, int max) {
: if (node == null)
: return true;
: if (node.data < min || node.data > max)
: return false;
: return isBST(node.left, min, node.data)
: && isBST(node.right, node.data + 1, max);
: }
|
H****s
发帖数: 247 | 17 BT node 有 parent 指针没？如果有，就可以不用stack area. |
a*******6
发帖数: 520 | 18 怎么觉得凡是递归就用了至少logn的额外空间啊，怎么做到O(1)呢？
【在 A**u 的大作中提到】
: 好方法
|
A**u
发帖数: 2458 | 19 无解
【在 a*******6 的大作中提到】
: 怎么觉得凡是递归就用了至少logn的额外空间啊，怎么做到O(1)呢？
|
