[CareerCup 4.1] Check whether a tree is balanced 書上答案似乎有錯誤

career 4.1
題目：Implement a function to check if a tree is balanced.  For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one .

對於上面的tree，root左邊是 height=2的subtree，是balanced的；root右邊是 height =3的subtree，是balanced；所以整個tree是balanced。

或者可參考 http://www.cs.auckland.ac.nz/~jmor159/PLDS210/AVL.html， 裡面有類似的例子

我們再看 careercup書上的答案 對於上面的 tree， 返回的是not balanced。

代碼如下：  

int min_depth( Node * root ) {
    if( !root )   return 0;

    return 1 + min( min_depth( root->left ),
                          min_depth( root->right ));
}

int max_depth( Node * root ) {
    if( !root )   return 0;

    return 1 + max( max_depth( root->left ),
                            max_depth( root->right ));
}

bool is_balanced( Node * root ) {
    return ( max_depth( root ) - min_depth( root ) ) <= 1
}
上面的代碼之所以不對，是因為 min_depth=1， max_depth =3 , 返回的 not balanced.
判讀 tree是否balanced，應該看 左邊 max_depth 和 右邊 max_depth 的差，而不是min_depth 和 max_depth 的差。

我們再看 careercup 書上對於balanced的定義：a balanced tree is a tree which has no two leaf nodes differ in distance from the root by more than one .
我們可以找到一個反例，說明這個定義是錯誤的：如下圖，有2個leafs，高度差為0，但整個 tree 是unbalanced，原因是第二行的節點左右的subtree的高度不同。

我認為以下的代碼應該才是正確的解法
int treeHeightBalanced(NODE* p)
{
    int leftHeight;
    int rightHeight;
    if(p==NULL) return 0;// balanced

    leftHeight = treeHeightBalanced(p->left) ;
    rightHeight = treeHeightBalanced(p->right) ;

    if(leftHeight==-1 || rightHeight==-1)
          return -1; //unbalanced
    if(leftHeight- rightHeight >1 || leftHeight- rightHeight <-1)
          return -1; //  unbalanced

     return 1+max(leftHeight,rightHeight); // balanced
}

不平衡的 你的root->left没有right child所以这个节点就被认为是最小距离了，层数为1  你的root -> right -> right -> right 层数为3， 所以根据定义不平衡

geniusroger2000 发表于 2013-2-15 06:02
不平衡的 你的root->left没有right child所以这个节点就被认为是最小距离了，层数为1  你的root -> right - ...

我添加了圖，那個tree是平衡的，AVL tree的定義：In an AVL tree, the heights of the two child subtrees of any node differ by at most one

怎么看好像都不平衡吧，我记得depth和leave children的差距是1。。

右边赶脚不能再转了，要转的话就变成

8-11-5 (left > right 不行）

如果这里成立的话，最下面的5可以移到左边的右边去。。

brilight 发表于 2013-2-15 06:59
我添加了圖，那個tree是平衡的，看AVL tree的定義

我明白你的意思了 书上的解法把只有一个子节点的也当成叶节点了 min_depth和max_depth函数定义有问题 你是这个意思么？

geniusroger2000 发表于 2013-2-15 09:39
我明白你的意思了 书上的解法把只有一个子节点的也当成叶节点了 min_depth和max_depth函数定义有问题 你是 ...

應該是這個意思~

brilight 发表于 2013-2-15 09:47
應該是這個意思~

嗯 书上主要是min_depth有问题

brilight 发表于 2013-2-15 10:04
超兄你也在上ECE259B吧，實在是太難了，我基本都不會啊。

是呀 太尼玛难了。。。。你现在投了哪些公司？