Macbook air with retina display??# Apple - 家有苹果
e*6
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 is_bst(root->left,min,root->a)&&is_bst(root->right,root->a,max);
}
我不错的评价。。记得上次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 is_bst(root->left,min,root->a)&&is_bst(root->right,root->a,max);
}
