e**********6
发帖数: 78 | 1 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
此由衷的对海内外所有华夏儿女表示感谢。。。
题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
检查一个bs是否为一个bst。
这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
家有兴趣的话可以讨论一下。
bool is_bst(BTNODE *root, int min, int max){
if(!root)
return true;
if(root->a>max || root->a
return false;
return is_bst(root->left,min,root->a)&&is_bst(root->right,root->a,max);
} |
e**********6
发帖数: 78 | 2 我来本版时间不长，但是后来发现这里氛围很好，就经常来。。
希望大家都早日找到工作。。 |
B*****g
发帖数: 34098 | 3 ding
题。
【在 e**********6 的大作中提到】
: 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
: 我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
: 此由衷的对海内外所有华夏儿女表示感谢。。。
: 题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
: 检查一个bs是否为一个bst。
: 这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
: 当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
: 我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
: ，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
: 下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
|
h**********d
发帖数: 4313 | 4 thanks for sharing
刚看题我也想错了，呵呵
题。
【在 e**********6 的大作中提到】
: 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
: 我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
: 此由衷的对海内外所有华夏儿女表示感谢。。。
: 题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
: 检查一个bs是否为一个bst。
: 这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
: 当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
: 我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
: ，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
: 下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
|
r*******l
发帖数: 511 | 5 Another solution is to do an in-order traversal of the binary tree, and
verify that the previous value (can be passed into the recursive function as
reference) is less than the current value. This works because when you do
an in-order traversal on a BST, the elements must be strictly in increasing
order. This method also runs in O(N) time and O(1) space.
bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
if (!p) return true;
return (isBSTInOrderHelper(p->left, prev) &&
(p->data > prev) && (prev = p->data) &&
isBSTInOrderHelper(p->right, prev));
}
bool isBSTInOrder(BinaryTree *root) {
int prev = INT_MIN;
return isBSTInOrderHelper(root, prev);
}
【在 h**********d 的大作中提到】
: thanks for sharing
: 刚看题我也想错了，呵呵
:
: 题。
|
d**e
发帖数: 6098 | 6 你的代码正确吧，我觉得这个是最简单的。
题。
【在 e**********6 的大作中提到】
: 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
: 我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
: 此由衷的对海内外所有华夏儿女表示感谢。。。
: 题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
: 检查一个bs是否为一个bst。
: 这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
: 当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
: 我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
: ，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
: 下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
|
e**********6
发帖数: 78 | 7
确实是很简单，只有一个小陷阱。。我平时写它也不会错。。面试的时候什么都有可能
发生。。
【在 d**e 的大作中提到】
: 你的代码正确吧，我觉得这个是最简单的。
:
: 题。
|
e**********6
发帖数: 78 | 8 是的。
as
increasing
【在 r*******l 的大作中提到】
: Another solution is to do an in-order traversal of the binary tree, and
: verify that the previous value (can be passed into the recursive function as
: reference) is less than the current value. This works because when you do
: an in-order traversal on a BST, the elements must be strictly in increasing
: order. This method also runs in O(N) time and O(1) space.
: bool isBSTInOrderHelper(BinaryTree *p, int& prev) {
: if (!p) return true;
: return (isBSTInOrderHelper(p->left, prev) &&
: (p->data > prev) && (prev = p->data) &&
: isBSTInOrderHelper(p->right, prev));
|
g*********s
发帖数: 1782 | 9 two phone interviews? can u share those fundamental ones?
for problem 1, why not just in-order traverse? O(N) and no trick at all.
题。
【在 e**********6 的大作中提到】
: 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
: 我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
: 此由衷的对海内外所有华夏儿女表示感谢。。。
: 题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
: 检查一个bs是否为一个bst。
: 这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
: 当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
: 我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
: ，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
: 下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
|
h**********d
发帖数: 4313 | 10 再问下楼主那两个arg min 和max是什么？第一个数和最后一个？谢谢
楼上inorder那个方法应该是最优的
题。
【在 e**********6 的大作中提到】
: 打来电话的是一个台湾MM，看到我是Chinese就对我非常好，快到结束时告诉我她会给
: 我不错的评价。。记得上次Google Interviewing Process遇到Chinese也都非常好，在
: 此由衷的对海内外所有华夏儿女表示感谢。。。
: 题目大多很简单，比较很碎，对基础稍微有一点点要求。下面我就集中说一下最后一题。
: 检查一个bs是否为一个bst。
: 这道题有一个陷阱，就是不可以只检查当前节点的左右子节点，因为根据bst的定义：
: 当前节点的左子树一定要都小于她本身，右子树一定都大于她本身。。
: 我一开始做，因为前面答的还可以，写到这里有点得意忘形，结果写错了。。经她提醒
: ，有点慌乱（没想到会错），之后为了稳妥，改出了一个必定正确的版本，但是效率低
: 下（O(n^2)）。挂下电话想一想其实本来很简单。。这里我给一个代码抛砖引玉。。大
|
|
|
d**e
发帖数: 6098 | 11 是一个范围。
比如node的value是int，那么各取int的最大值和最小值。
root->value就在这个范围内。
左子树就在int_min和root->value
右子树就在root->value和int_max
【在 h**********d 的大作中提到】
: 再问下楼主那两个arg min 和max是什么？第一个数和最后一个？谢谢
: 楼上inorder那个方法应该是最优的
:
: 题。
|
h**6
发帖数: 4160 | 12 ... && (prev = p->data) && ...
如果刚好有个结点值为0怎么办呢 |
e**********6
发帖数: 78 | 13 这个问题指的好。
【在 h**6 的大作中提到】
: ... && (prev = p->data) && ...
: 如果刚好有个结点值为0怎么办呢
|
e**********6
发帖数: 78 | 14 bool is_bst_inorder(BTNODE *root, int &prev){
if(!root)
return true;
bool vb1,vb2;
vb1=is_bst_inorder(root->left,prev);
if(prev>root->a)
return false;
prev=root->a;
vb2=is_bst_inorder(root->right,prev);
return vb1&&vb2;
} |
d**e
发帖数: 6098 | 15 han6果然好眼力！
其实那一步是多余的吧，直接把root->data代到最后一个helper function作参数可以
了。
【在 e**********6 的大作中提到】
: 这个问题指的好。
|
e**********6
发帖数: 78 | 16 我感觉这两种方法应该在时间复杂度上完全相同的
【在 h**********d 的大作中提到】
: 再问下楼主那两个arg min 和max是什么？第一个数和最后一个？谢谢
: 楼上inorder那个方法应该是最优的
:
: 题。
|
h**********d
发帖数: 4313 | 17 明白了，谢谢
【在 d**e 的大作中提到】
: 是一个范围。
: 比如node的value是int，那么各取int的最大值和最小值。
: root->value就在这个范围内。
: 左子树就在int_min和root->value
: 右子树就在root->value和int_max
|
f*******I
发帖数: 39 | 18 prev表示什么呢？
【在 e**********6 的大作中提到】
: bool is_bst_inorder(BTNODE *root, int &prev){
: if(!root)
: return true;
: bool vb1,vb2;
: vb1=is_bst_inorder(root->left,prev);
: if(prev>root->a)
: return false;
: prev=root->a;
: vb2=is_bst_inorder(root->right,prev);
: return vb1&&vb2;
|
i**********e
发帖数: 1145 | 19 http://www.ihas1337code.com/2010/09/determine-if-binary-tree-is-binary.html
谢谢你对这问题的指出。
已经发了两个包子给你了，请查收。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 h**6 的大作中提到】
: ... && (prev = p->data) && ...
: 如果刚好有个结点值为0怎么办呢
|
i**********e
发帖数: 1145 | 20 prev is the previously traversed node's value.
if in-order traversal produce a strictly increasing order of elements, it
must be a BST.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 f*******I 的大作中提到】
: prev表示什么呢？
|
