檢查二叉樹是否平衡

我在一本書中看到了這個問題（破解編碼採訪）。建議的代碼是：檢查二叉樹是否平衡

public boolean isBalanced(Node root) { 

    if(root == null) 
     return true; 

    int leftHeight = getHeight(root.left); 
    System.out.println("left height: " + leftHeight); 
    int rightHeight = getHeight(root.right); 
    System.out.println("right height: " + rightHeight); 
    int diff = Math.abs(leftHeight - rightHeight); 

    // check if difference in height is more than 1 
    if (diff > 1) 
     return false; 

    // check if left and right subtrees are balanced 
    else 
     return isBalanced(root.left) && isBalanced(root.right);

我不明白的是，爲什麼我們需要返回isBalanced（root.left）& & isBalanced（root.right）的一部分。僅僅是檢查高度並且如果高度超過1就返回錯誤還不夠，否則是正確的？

來源

2017-01-03 Stackimus Prime

在左右根上具有相等的高度並不能保證樹是平衡的。例如，我可以有一個左側高度爲6，右側高度爲6的根，但左側分支是沒有任何右側分支的單個分支。 – Compass

你怎麼能有一棵有3個以上節點的樹高不能超過1？ – NickL

不，這是不夠的，只是爲了檢查高度並返回false如果高度超過1，和真正否則。簡單地檢查根的高度會導致誤報如下：

 A 
    /\ 
     B F 
    //
    C G 
//
    D H 
//
E I

來源

2017-01-03 19:57:02

好的。感謝您清理東西！ –

檢查二叉樹是否平衡

回答

相關問題