c**a
发帖数: 316 | 1 how test a BST is balanced or not? |
c*****t
发帖数: 1879 | 2 What is the definition of "balanced" BST? That should give you the
answer.
【在 c**a 的大作中提到】
: how test a BST is balanced or not?
|
c**a
发帖数: 316 | 3 深度之差 小于等于 1
【在 c*****t 的大作中提到】
: What is the definition of "balanced" BST? That should give you the
: answer.
|
c*****t
发帖数: 1879 | 4 你先搞清楚这是什么的深度之差。这个 balanced 的定义一般都很详细的。
【在 c**a 的大作中提到】
: 深度之差 小于等于 1
|
c**a
发帖数: 316 | 5 任何一个子树的 左子树 和右子树 的深度 差 不超过1.。
【在 c*****t 的大作中提到】
: 你先搞清楚这是什么的深度之差。这个 balanced 的定义一般都很详细的。
|
c*****t
发帖数: 1879 | 6 这不已经告诉你怎么算了么？有什么疑问么？
【在 c**a 的大作中提到】
: 任何一个子树的 左子树 和右子树 的深度 差 不超过1.。
|
c**a
发帖数: 316 | 7 这个程序不好写啊。。。
【在 c*****t 的大作中提到】
: 这不已经告诉你怎么算了么？有什么疑问么？
|
t****t
发帖数: 6806 | 8 哪里不好写?
是不会计算子树深度?
还是不会计算子树深度之差?
还是不会计算每个节点的子树深度之差?
【在 c**a 的大作中提到】
: 这个程序不好写啊。。。
|
b******s
发帖数: 2 | 9 int isBTbalanced(node* pTree)
{
if(pTree == NULL)
return 0;
int dleft = isBTblanced(pTree->left);
int dright = isBTblanced(pTree->right);
if(dleft>=0 && dright >=0)
{
if(dleft>dright && dleft-dright<=1)
return dleft;
if(dleft
return dright;
}
return -1;
}
【在 c**a 的大作中提到】
: 这个程序不好写啊。。。
|
c*****t
发帖数: 1879 | 10 buggy. You forgot the case where dleft == dright.
【在 b******s 的大作中提到】
: int isBTbalanced(node* pTree)
: {
: if(pTree == NULL)
: return 0;
:
: int dleft = isBTblanced(pTree->left);
: int dright = isBTblanced(pTree->right);
: if(dleft>=0 && dright >=0)
: {
: if(dleft>dright && dleft-dright<=1)
|
b******s
发帖数: 2 | |
b******y
发帖数: 9224 | 12 牛啊。搞的我都想在剑知小站上面专门搞个算法题的label啦。 |
