I**A
发帖数: 2345 | 1 KG说要找左MAX，右MIN，有什么优势麽？
同学们，帮我看看，我下面的方法，有问题麽?
public static boolean isBST(Node node){
Node anode = node;
if((anode == null) || ((anode.leftchild==null) && (anode.rightchild=
=null)))
return true;
//if there is left child or right child or both
//if both of them are not null
if ((anode.leftchild!=null) && (anode.rightchild!=null))
if ((anode.data>anode.leftchild.data) && (anode.data<=anode.
rightchild.data))
ret |
p******n
发帖数: 32 | 2 no problem using recursive algorithm as the solution. But your code is
not clean enough.
(anode.rightchild=
【在 I**A 的大作中提到】
: KG说要找左MAX，右MIN，有什么优势麽？
: 同学们，帮我看看，我下面的方法，有问题麽?
: public static boolean isBST(Node node){
: Node anode = node;
: if((anode == null) || ((anode.leftchild==null) && (anode.rightchild=
: =null)))
: return true;
: //if there is left child or right child or both
: //if both of them are not null
: if ((anode.leftchild!=null) && (anode.rightchild!=null))
|
I**A
发帖数: 2345 | 3 哈哈哈，真的真的，我也觉得是， 逻辑上很清楚，可是写起来很奇怪。。
有高见没？
【在 p******n 的大作中提到】
: no problem using recursive algorithm as the solution. But your code is
: not clean enough.
:
: (anode.rightchild=
|
Z*****Z
发帖数: 723 | 4 天使同学，这个有问题吧？好像不能只检查左孩子比当前值小。(左孩子可能有个右孩子
比当前值大）
rightchild=
【在 I**A 的大作中提到】
: KG说要找左MAX，右MIN，有什么优势麽？
: 同学们，帮我看看，我下面的方法，有问题麽?
: public static boolean isBST(Node node){
: Node anode = node;
: if((anode == null) || ((anode.leftchild==null) && (anode.rightchild=
: =null)))
: return true;
: //if there is left child or right child or both
: //if both of them are not null
: if ((anode.leftchild!=null) && (anode.rightchild!=null))
|
I**A
发帖数: 2345 | 5 晕
你说的对。。。
孩子
【在 Z*****Z 的大作中提到】
: 天使同学，这个有问题吧？好像不能只检查左孩子比当前值小。(左孩子可能有个右孩子
: 比当前值大）
:
: rightchild=
|
Z*****Z
发帖数: 723 | 6 that's the real reason of KG's words
【在 I**A 的大作中提到】
: 晕
: 你说的对。。。
:
: 孩子
|
l******4
发帖数: 729 | 7 先检查是不是binary heap
孩子
【在 Z*****Z 的大作中提到】
: 天使同学，这个有问题吧？好像不能只检查左孩子比当前值小。(左孩子可能有个右孩子
: 比当前值大）
:
: rightchild=
|
I**A
发帖数: 2345 | 8 找MAX复杂度是多少？
【在 Z*****Z 的大作中提到】
: that's the real reason of KG's words
|
s***e
发帖数: 793 | 9 这个题最简单就是中序遍历改一改
bool IsBst(node * n, int & min)
{
if(!n) return true;
if(!IsBst(n->left, min))return false;
return (n->value > min )? IsBst(n->right,min=n->value) : false ;
}
when call it, just call it like
isBst(root,tmp=std::numeric_limits::min());
rightchild=
【在 I**A 的大作中提到】
: KG说要找左MAX，右MIN，有什么优势麽？
: 同学们，帮我看看，我下面的方法，有问题麽?
: public static boolean isBST(Node node){
: Node anode = node;
: if((anode == null) || ((anode.leftchild==null) && (anode.rightchild=
: =null)))
: return true;
: //if there is left child or right child or both
: //if both of them are not null
: if ((anode.leftchild!=null) && (anode.rightchild!=null))
|
I**A
发帖数: 2345 | 10 我是已经晕了
有人提反对意见麽？
【在 s***e 的大作中提到】
: 这个题最简单就是中序遍历改一改
: bool IsBst(node * n, int & min)
: {
: if(!n) return true;
: if(!IsBst(n->left, min))return false;
: return (n->value > min )? IsBst(n->right,min=n->value) : false ;
: }
: when call it, just call it like
: isBst(root,tmp=std::numeric_limits::min());
:
|
|
|
s***e
发帖数: 793 | 11 made a small change to be more compact
【在 I**A 的大作中提到】
: 我是已经晕了
: 有人提反对意见麽？
|
I**A
发帖数: 2345 | 12 这个程序这种情况下成不？
就是把我反驳到的那个if the leftchild has a rightchild which has a node
larger than the current node.
【在 s***e 的大作中提到】
: made a small change to be more compact
|
s***e
发帖数: 793 | 13 sure, write an in-order tree traversal code and you will get the idea
the only difference is that, when you traverse, you just call print(
currentnode->data) , instead of printing out value. The code is like you
compare previous value with current one, and update the value
【在 I**A 的大作中提到】
: 这个程序这种情况下成不？
: 就是把我反驳到的那个if the leftchild has a rightchild which has a node
: larger than the current node.
|
g*******y
发帖数: 1930 | 14 you need to have both 'min' and 'max' as parameter
【在 s***e 的大作中提到】
: 这个题最简单就是中序遍历改一改
: bool IsBst(node * n, int & min)
: {
: if(!n) return true;
: if(!IsBst(n->left, min))return false;
: return (n->value > min )? IsBst(n->right,min=n->value) : false ;
: }
: when call it, just call it like
: isBst(root,tmp=std::numeric_limits::min());
:
|
s***e
发帖数: 793 | 15 why?
Actually , i should name min as currentvalue
【在 g*******y 的大作中提到】
: you need to have both 'min' and 'max' as parameter
|
g*******y
发帖数: 1930 | 16 consider a sub-tree in BST, in general, all the nodes in the subtree must
have
values within a range: [min, max]
【在 s***e 的大作中提到】
: why?
: Actually , i should name min as currentvalue
|
s***e
发帖数: 793 | 17 the code is just doing in-order traverse and check whether the sequence is
strictly increasing or not.
【在 g*******y 的大作中提到】
: consider a sub-tree in BST, in general, all the nodes in the subtree must
: have
: values within a range: [min, max]
|
I**A
发帖数: 2345 | 18 好像不太一样哎
比如
4
/
3
/ \
1 5
你的code返回true or false?
不行了，挺不住了。。。
明儿见
【在 s***e 的大作中提到】
: sure, write an in-order tree traversal code and you will get the idea
: the only difference is that, when you traverse, you just call print(
: currentnode->data) , instead of printing out value. The code is like you
: compare previous value with current one, and update the value
|
I**A
发帖数: 2345 | 19 哦，那这个逻辑应该是通的。。
我自己都不记得了，这个题目是以前的一个，好像里面要求了不要inorder traverse，
是这么回事儿麽？
【在 s***e 的大作中提到】
: the code is just doing in-order traverse and check whether the sequence is
: strictly increasing or not.
|
s***e
发帖数: 793 | 20 你不睡觉了么，咋回来改题目了，革命的本钱最重要
【在 I**A 的大作中提到】
: 哦，那这个逻辑应该是通的。。
: 我自己都不记得了，这个题目是以前的一个，好像里面要求了不要inorder traverse，
: 是这么回事儿麽？
|
|
|
g*******y
发帖数: 1930 | 21 You wants to compare every node with its predecessor, fine. But there are
implicit stack push/pop operations that you didn't take into account.
In the traditional in-order traversal printing algorithm, when a node is
printed out, the function call stack may be then popped for several times,
before the you print out the next node.
Now you see why your code doesn't work: no information(value) is recorded when
the function call stack is popped.
If you insist applying this idea, it's better to use
【在 s***e 的大作中提到】
: the code is just doing in-order traverse and check whether the sequence is
: strictly increasing or not.
|
s***e
发帖数: 793 | 22 1) int&
2) if 1) does not explain, i did not understand your point
when
in-
【在 g*******y 的大作中提到】
: You wants to compare every node with its predecessor, fine. But there are
: implicit stack push/pop operations that you didn't take into account.
: In the traditional in-order traversal printing algorithm, when a node is
: printed out, the function call stack may be then popped for several times,
: before the you print out the next node.
: Now you see why your code doesn't work: no information(value) is recorded when
: the function call stack is popped.
: If you insist applying this idea, it's better to use
|
g*******y
发帖数: 1930 | 23 不好意思我没注意你的'&' ......
现在态度不端正，看code都瞟一眼就过...
【在 s***e 的大作中提到】
: 1) int&
: 2) if 1) does not explain, i did not understand your point
:
: when
: in-
|
