"Hacking a G Interview"怎么有这样低级错？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

"Hacking a G Interview"怎么有这样低级错？

"Hacking a G Interview"怎么有这样低级错？# JobHunting - 待字闺中

K*k2011-11-18 08:11

1 楼

判断BT是否BST, 给的代码如下。
看不明白，如果传入的是空树也就是curr为null
curr.left不就crash了？
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;
}
相比下，SEwind520 (东南枫)的方法就靠谱的多
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, max);
}

a*m2011-11-18 08:11

2 楼

这个是c++代码么？

K*k2011-11-18 08:11

3 楼

看去都是Java的，很容易改为C++
但是Java对null进行引用取值也是有问题的吧？反正C/C++的基本就是segmentation
fault.

【在 a********m 的大作中提到】

: 这个是c++代码么？

f*t2011-11-18 08:11

4 楼

java的话会抛异常
面经给的答案经常不完全正确，千万要自己写，别背代码……
比如你这个帖：http://www.mitbbs.com/article_t/JobHunting/31990427.html
今天想了一下，我的代码改过后还有bug……

【在 K*****k 的大作中提到】

: 看去都是Java的，很容易改为C++
: 但是Java对null进行引用取值也是有问题的吧？反正C/C++的基本就是segmentation
: fault.

e*l2011-11-18 08:11

5 楼

如果主函数这么调用helper就不会有null的情况，你看看书上怎么写的
boolean isValid(Node root){
if(root==null) return true;
else return isValidHelper(root, INT_MIN, INT_MAX);
}

K*k2011-11-18 08:11

6 楼

可惜，Hacking a G Interview没能像你那样写
 boolean isValid(Node root) {
return isValidHelper(root, Integer.MIN_VALUE,
Integer.MAX_VALUE);
}

【在 e***l 的大作中提到】

: 如果主函数这么调用helper就不会有null的情况，你看看书上怎么写的
: boolean isValid(Node root){
: if(root==null) return true;
: else return isValidHelper(root, INT_MIN, INT_MAX);
: }