g***x
发帖数: 494 | 1 which of below is incorrect?
方法1.
int getheight(node r)
{
if r==0 return 0;
return max(getheight(r.left),getheight(r.right))+1;
}
bool checkbalance(node r)
{
if r==0 return true;
int diff=getheight(r.left)-getheight(r.right)
if | diff|>1 return false;
else
return checkbalance(r.left)&&checkbalance(r.right);
}
方法2.
int getmaxheight(node r)
{
if r==0 return 0;
else
return max(getmaxheight(r.left),getmaxheight(r.right))+1;
}
int getminheight(node r)
{
if r==0 return 0;
else
return min(getminheight(r.left),getminheight(r.right))+1;
}
bool checkbalance(node r)
{
if getmaxheight(root)-getminheight(root)<=1 return true;
else
return false;
}
方法2看似是不是有点问题？ | l********e
发帖数: 34 | 2 Method 2, getminheight will always return 1.
Thus is not correct.
【在 g***x 的大作中提到】
: which of below is incorrect?
: 方法1.
: int getheight(node r)
: {
: if r==0 return 0;
: return max(getheight(r.left),getheight(r.right))+1;
: }
: bool checkbalance(node r)
: {
: if r==0 return true;
| y**********u
发帖数: 6366 | 3 Really?
【在 l********e 的大作中提到】
: Method 2, getminheight will always return 1.
: Thus is not correct.
| g***x
发帖数: 494 | 4 能举例说明吗？
【在 l********e 的大作中提到】
: Method 2, getminheight will always return 1.
: Thus is not correct.
| l********e
发帖数: 34 | 5 Ah, sorry, I was wrong.
Please ignore me....
【在 g***x 的大作中提到】
: 能举例说明吗？
| g*****i
发帖数: 2162 | 6 我觉得得看怎么定义balanced tree
如果定义是任意两个叶子节点的高度差不能大于1,那么方法二正确,方法一错误.
如果定义是左右子树都平衡,并且高度差不能大于1,那么方法一正确,方法二错误.
总的来说方法二更严格些. | c**m
发帖数: 535 | 7 好吧，对于不同的balanced的定义，确实有不同的解法。
但就针对定义1：任意两个叶子节点的高度差不能大于1，方法二也不是正确的
问题在于minDepth()上面
举一个例子，如果一个树是：
N
/ \
N N
/ \
N N
/ \
N N
只有两个叶子，而且高度相同，应该算是balanced
但root的maxdepth/mindepth使用方法二计算出的是4/2，应为左右两个path都是
1/1，2/1，3/1
对于定义2，方法一是正确的。
对于定义1，它比定义2更加严格一些，两个方法都不正确。
另外，LZ是不是看了这个post？
http://stackoverflow.com/questions/742844/how-to-determine-if-b
【在 g*****i 的大作中提到】
: 我觉得得看怎么定义balanced tree
: 如果定义是任意两个叶子节点的高度差不能大于1,那么方法二正确,方法一错误.
: 如果定义是左右子树都平衡,并且高度差不能大于1,那么方法一正确,方法二错误.
: 总的来说方法二更严格些.
|
|
