K*****u
发帖数: 241 | 1 判断一棵二叉树是否平衡
在第五版前Gayle认为只需要判断最高深度和最低深度的值是否相差不超过1就可以。
解法虽然简单，但偷换了概念，是错误的
虽然最高深度和最低深度的值相差不超过1的树一定是平衡的，但反过来却不对。换句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非 必要 条件
也就是说那个解法偷换成了更强的要求（虽然解法更简单)，但这样的树只是平衡树的一个真子集。
请大家自行构造一棵最大深度和最小深度的值超过1的二叉平衡树，加深对二叉平衡树概念的理解。 |
B*******1
发帖数: 2454 | |
K*****u
发帖数: 241 | 3 5th edition
【在 B*******1 的大作中提到】
: 在哪里修正的啊？
|
h*****n
发帖数: 93 | |
m*******l
发帖数: 12782 | 5 amazon也不过30多块
【在 h*****n 的大作中提到】
: 求第五版.可以提供host空间.
|
c*****e
发帖数: 3226 | 6 把这个题的答案帖一下吧。
句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非
必要 条件
的一个真子集。
树概念的理解。
【在 K*****u 的大作中提到】
: 判断一棵二叉树是否平衡
: 在第五版前Gayle认为只需要判断最高深度和最低深度的值是否相差不超过1就可以。
: 解法虽然简单，但偷换了概念，是错误的
: 虽然最高深度和最低深度的值相差不超过1的树一定是平衡的，但反过来却不对。换句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非 必要 条件
: 也就是说那个解法偷换成了更强的要求（虽然解法更简单)，但这样的树只是平衡树的一个真子集。
: 请大家自行构造一棵最大深度和最小深度的值超过1的二叉平衡树，加深对二叉平衡树概念的理解。
|
m***n
发帖数: 2154 | |
l*****y
发帖数: 56 | 8 ht 是一个测深度的函数， 如果在某个结点两个子树的深度相差大于1就返回－1， 否
则返回两个子数的最大深度。
不知道有没有问题，请指教。
int ht(Node p){
if (!p) return 0; /* 之前写成1了，应该是0.
int L=ht(p.left);
int R=ht(p.right);
if (L!=-1 && R!= -1 && abs(L-R)<=1 ) return max(L+1, R+1);
else return -1;
}
int main(){
Node p;
if(ht(P)!=-1) cout<<"It is balanced!\n";
}
【在 c*****e 的大作中提到】
: 把这个题的答案帖一下吧。
:
: 句话说，二叉树最高深度和最低深度的值相差不超过1 是 二叉平衡树 的 充分 而非
: 必要 条件
: 的一个真子集。
: 树概念的理解。
|
