检查二叉树是否平衡

hsvhsicv  于 2021-07-09  发布在  Java
关注(0)|答案(1)|浏览(447)

我在一本书中看到了这个问题(破解编码面试)。建议代码为:

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);

我不明白的是为什么我们需要returnisbalanced(root.left)和&isbalanced(root.right)。仅仅检查高度就足够了吗?如果高度大于1,返回false,否则返回true?

cl25kdpy

cl25kdpy1#

不,仅检查高度是不够的,如果高度大于1,则返回false,否则返回true。简单地检查根的高度会导致如下误报:

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

相关问题