检查二叉树是否平衡

我在一本书中看到了这个问题（破解编码采访）。建议的代码是：检查二叉树是否平衡

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

好的。感谢您清理东西！ –

检查二叉树是否平衡

回答

相关问题