n********u
发帖数: 194 | 1 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
∩)O哈哈~
贴一下我的code，应该是没有大错啊，真是郁闷
boolean isBinaryTree(Node root){
if(root == null) return true;
else if((root.left == null) && (root.right == null))
return true;
else if ((root.value <= root.left.value) && (root.value > root.right.value
))
return (isBinartTree(root.left) && isBinaryTree(root.right));
|
H*M
发帖数: 1268 | 2 这个不是讨论过吗
你写的应该是不对的
check this:
3
2 5
1 20
recursive
【在 n********u 的大作中提到】
: 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
: 行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
: function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
: 于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
: ∩)O哈哈~
: 贴一下我的code，应该是没有大错啊，真是郁闷
: boolean isBinaryTree(Node root){
: if(root == null) return true;
: else if((root.left == null) && (root.right == null))
: return true;
|
g*******y
发帖数: 1930 | |
r**u
发帖数: 1567 | 4 你这个问题问的。。。
recursive
【在 n********u 的大作中提到】
: 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
: 行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
: function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
: 于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
: ∩)O哈哈~
: 贴一下我的code，应该是没有大错啊，真是郁闷
: boolean isBinaryTree(Node root){
: if(root == null) return true;
: else if((root.left == null) && (root.right == null))
: return true;
|
n********u
发帖数: 194 | 5 那应该是怎样呢(⊙o⊙)？
算了，就当练习吧。
【在 g*******y 的大作中提到】
: 你这个code不对啊
|
g*******y
发帖数: 1930 | 6 奇怪，一般面试官至少会指出你的错误，然后让你慢慢改正啊。怎么你的面试官直接3
分钟就结束了？是不是楼主表现的有点arrogant？这个是大忌
recursive
【在 n********u 的大作中提到】
: 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
: 行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
: function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
: 于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
: ∩)O哈哈~
: 贴一下我的code，应该是没有大错啊，真是郁闷
: boolean isBinaryTree(Node root){
: if(root == null) return true;
: else if((root.left == null) && (root.right == null))
: return true;
|
n********u
发帖数: 194 | 7 嘻嘻，他指出了，就刚才谁谁给的那个例子，如果只有一个child呢，于是我很雷人地
在第三个if else加了两个|| 来判断如果只有left child和right child。他也没说什
么啊，我承认code是看着很难看，但是也算是在改正我的错误。唉，所以你看我最后不
是直接问他要是fail了，什么时候能再重投简历来着。
3
【在 g*******y 的大作中提到】
: 奇怪，一般面试官至少会指出你的错误，然后让你慢慢改正啊。怎么你的面试官直接3
: 分钟就结束了？是不是楼主表现的有点arrogant？这个是大忌
:
: recursive
|
l*******r
发帖数: 511 | 8 应该是traverse in order,然后看看是不是ascending的对吧
3
【在 g*******y 的大作中提到】
: 奇怪，一般面试官至少会指出你的错误，然后让你慢慢改正啊。怎么你的面试官直接3
: 分钟就结束了？是不是楼主表现的有点arrogant？这个是大忌
:
: recursive
|
k***e
发帖数: 556 | 9 seems to be wrong :)
recursive
【在 n********u 的大作中提到】
: 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
: 行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
: function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
: 于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
: ∩)O哈哈~
: 贴一下我的code，应该是没有大错啊，真是郁闷
: boolean isBinaryTree(Node root){
: if(root == null) return true;
: else if((root.left == null) && (root.right == null))
: return true;
|
g*******y
发帖数: 1930 | 10 不光是只有一个child的问题，还有更严重的问题
move on吧，估计你也是刚开始找工作，以后多练习 :p
【在 n********u 的大作中提到】
: 嘻嘻，他指出了，就刚才谁谁给的那个例子，如果只有一个child呢，于是我很雷人地
: 在第三个if else加了两个|| 来判断如果只有left child和right child。他也没说什
: 么啊，我承认code是看着很难看，但是也算是在改正我的错误。唉，所以你看我最后不
: 是直接问他要是fail了，什么时候能再重投简历来着。
:
: 3
|
|
|
H*M
发帖数: 1268 | 11 连我也看出你的傲慢了。。呵呵
【在 n********u 的大作中提到】
: 嘻嘻，他指出了，就刚才谁谁给的那个例子，如果只有一个child呢，于是我很雷人地
: 在第三个if else加了两个|| 来判断如果只有left child和right child。他也没说什
: 么啊，我承认code是看着很难看，但是也算是在改正我的错误。唉，所以你看我最后不
: 是直接问他要是fail了，什么时候能再重投简历来着。
:
: 3
|
s*****r
发帖数: 773 | 12 啥问题？
【在 g*******y 的大作中提到】
: 不光是只有一个child的问题，还有更严重的问题
: move on吧，估计你也是刚开始找工作，以后多练习 :p
|
l*******r
发帖数: 511 | 13 root的左指数应该都小于root
【在 s*****r 的大作中提到】
: 啥问题？
|
a******2
发帖数: 393 | 14 要判断指针为空先？
【在 s*****r 的大作中提到】
: 啥问题？
|
H*M
发帖数: 1268 | 15 ..
我不是给出个反例了吗？
【在 a******2 的大作中提到】
: 要判断指针为空先？
|
s*****r
发帖数: 773 | 16 那就是那个例子的问题吧
【在 l*******r 的大作中提到】
: root的左指数应该都小于root
|
n********u
发帖数: 194 | 17 嘻嘻，我不傲慢，我其实很差的，只是一开始他就问我你在某某州读书，但是你resume
上的地址又是另一个州，我就解释，我说我lg在那边，我的确是比较prefer那个州的工
作。但是，但是，你们公司这么大，有offer我肯定来的。
呵呵，继续找，继续学习。
【在 H*M 的大作中提到】
: 连我也看出你的傲慢了。。呵呵
|
B*****i
发帖数: 831 | 18 这么说一般公司都不行的，
似乎既不能说出来“有offer我肯定来”这种话，
也不能表达出有其他更优选择的意思。
resume
【在 n********u 的大作中提到】
: 嘻嘻，我不傲慢，我其实很差的，只是一开始他就问我你在某某州读书，但是你resume
: 上的地址又是另一个州，我就解释，我说我lg在那边，我的确是比较prefer那个州的工
: 作。但是，但是，你们公司这么大，有offer我肯定来的。
: 呵呵，继续找，继续学习。
|
s*****r
发帖数: 773 | 19 应该说，我就认定你了
跟找媳妇一样的
【在 B*****i 的大作中提到】
: 这么说一般公司都不行的，
: 似乎既不能说出来“有offer我肯定来”这种话，
: 也不能表达出有其他更优选择的意思。
:
: resume
|
B*****i
发帖数: 831 | 20 没错，但是我感觉"我认定你"这种气势不能说出来，
得通过言行举止让他们强烈的感觉到，呵呵
【在 s*****r 的大作中提到】
: 应该说，我就认定你了
: 跟找媳妇一样的
|
|
|
H*M
发帖数: 1268 | 21 你确实有点傲慢。以后注意改改吧
resume
【在 n********u 的大作中提到】
: 嘻嘻，我不傲慢，我其实很差的，只是一开始他就问我你在某某州读书，但是你resume
: 上的地址又是另一个州，我就解释，我说我lg在那边，我的确是比较prefer那个州的工
: 作。但是，但是，你们公司这么大，有offer我肯定来的。
: 呵呵，继续找，继续学习。
|
z*******y
发帖数: 578 | 22 这个判定BST的有两个解法，一个就是inorder 一下看看是不是升序的排列
另一个方法是 判断 根节点的值是不是大于左子树的最大值并且小于右子树的最小值，
递归实现。 |
t*********n
发帖数: 1292 | 23 除了这两个问题外，还有什么更严重的啊？
【在 g*******y 的大作中提到】
: 不光是只有一个child的问题，还有更严重的问题
: move on吧，估计你也是刚开始找工作，以后多练习 :p
|
g*******y
发帖数: 1930 | 24 前面人的回复里面已经说到了
【在 t*********n 的大作中提到】
: 除了这两个问题外，还有什么更严重的啊？
|
f****b
发帖数: 486 | 25 这个题出现频率很高，俺的AMZN电面也考了
你狠，居然问最后那个问题
recursive
【在 n********u 的大作中提到】
: 真是吐血，除了问我简历上的问题，就是一题判断是不是BST的coding 题目，让我一行
: 行报给他听。因为我上学期带data structure under的lab，我很熟悉这样的recursive
: function。3分钟写出来报给他，他就不理我了，说到此结束。然后问我有什么问题，
: 于是我问了一个让他也很吐血的问题，我说我要是fail了，得隔多久才能申请，O(∩_
: ∩)O哈哈~
: 贴一下我的code，应该是没有大错啊，真是郁闷
: boolean isBinaryTree(Node root){
: if(root == null) return true;
: else if((root.left == null) && (root.right == null))
: return true;
|
b******g
发帖数: 1721 | |
i****h
发帖数: 321 | 27 大牛，我写了一个，可是指针有问题，能不能帮我看看啊？谢谢。
bool isBST(TreeNode *n, int *max, int *min){
if(n == NULL){
max = NULL;
min = NULL;
return true;
}
int *lmax, *lmin;
int *rmax, *rmin;
bool leftResult = isBST(n->left, lmax, lmin);
bool rightResult = isBST(n->right, rmax, rmin);
if( leftResult && rightResult ){
if(lmax != NULL && n->value < *lmax )
return false;
if(rmin != NULL && n->va
【在 g*******y 的大作中提到】
: 不光是只有一个child的问题，还有更严重的问题
: move on吧，估计你也是刚开始找工作，以后多练习 :p
|
d****v
发帖数: 458 | 28 我不是大牛，我是小猪，这个是我写的
主要idea是rightMost不一定是左边的最大值，leftMost不一定是右边的最小值
但是没关系，root和他比就行了。
bool isBST(Node n)
{
if(n == null)
return true;
return isBST(n.left) && (n.left==null || n.value>rightMost(n.left))
&&
isBST(n.right) && (n.right==null || n.value
}
int/double rightMost(Node n)
{
if(n==null)
throw exception;
if(n.right==null)
return n.value;
return leftMax(n.right);
}
int/double leftMost(Node n)
{
if(n==null)
【在 i****h 的大作中提到】
: 大牛，我写了一个，可是指针有问题，能不能帮我看看啊？谢谢。
: bool isBST(TreeNode *n, int *max, int *min){
: if(n == NULL){
: max = NULL;
: min = NULL;
: return true;
: }
: int *lmax, *lmin;
: int *rmax, *rmin;
: bool leftResult = isBST(n->left, lmax, lmin);
|
g*******y
发帖数: 1930 | 29 < => <=
> => >=
时间性能不好
【在 d****v 的大作中提到】
: 我不是大牛，我是小猪，这个是我写的
: 主要idea是rightMost不一定是左边的最大值，leftMost不一定是右边的最小值
: 但是没关系，root和他比就行了。
: bool isBST(Node n)
: {
: if(n == null)
: return true;
: return isBST(n.left) && (n.left==null || n.value>rightMost(n.left))
: &&
: isBST(n.right) && (n.right==null || n.value
|
d****v
发帖数: 458 | 30 怎么improve？还是彻底改成排序看？
【在 g*******y 的大作中提到】
: < => <=
: > => >=
: 时间性能不好
|
|
|
n********u
发帖数: 194 | 31 嗯，昨晚才发现自己犯了一个致命的错误，就是前面有人提出来的，唉，太粗心了，我
知道应该怎么做的，搞得我昨晚睡觉都在做bst的梦。
开朗是假的，都是装出来的，找工作还是挺郁闷的。但是郁闷有什么用，还是要多多学
习，多在失败的interview里面涨经验。
下次碰到这个题目我知道该怎么做了(*^__^*) ……
【在 b******g 的大作中提到】
: 楼主很开朗啊，我喜欢。
: 祝你早日找到好工作！
|
n********u
发帖数: 194 | 32 我刚才写了一下，您看看有没有让code更neat一点的方法？
class BinaryTree{
private static class Node{
int value;
Node left;
Node right;
public Node(int value, Node left, Node right){
this.value=value;
this,left=left;
this.right=right;
}
}
private boolean isMax(Node root, Node lf){
if(root.value < lf.value)
return false;
else{
if ((lf.left == null)&&(lf.right == null))
return true;
else if ((lf.left == null) && (lf.right != null))
【在 z*******y 的大作中提到】
: 这个判定BST的有两个解法，一个就是inorder 一下看看是不是升序的排列
: 另一个方法是 判断 根节点的值是不是大于左子树的最大值并且小于右子树的最小值，
: 递归实现。
|
d****v
发帖数: 458 | 33 完全没看我写的啊
不是说了么比较rightMost和leftMost就行，不用找左右最大和最小的
就那个还有牛人说复杂呢
【在 n********u 的大作中提到】
: 我刚才写了一下，您看看有没有让code更neat一点的方法？
: class BinaryTree{
: private static class Node{
: int value;
: Node left;
: Node right;
:
: public Node(int value, Node left, Node right){
: this.value=value;
: this,left=left;
|
m******9
发帖数: 968 | |
