P39 判断二叉树是否平衡

描述#

这个题目说的是，给你一棵二叉树，你要判断它是否平衡。这里平衡指的是，对于树上任意一个节点，它的两棵子树的高度差不能大于 1。

比如说，给你的二叉树是：
 1

/   

2     4
/ 

8  16
它的任意节点的左右子树高度差都不大于 1，因此它是一棵平衡二叉树。
再比如说，给你的二叉树是：
 1

/   

2     4


8


16
在这棵树中，根节点的左右子树高度差为 2，因此它不是一棵平衡二叉树。

代码#

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  int getHeight(TreeNode root) {
    if (root == null) return 0;
    int left = getHeight(root.left);
    int right = getHeight(root.right);
    return Math.max(left, right) + 1;
  }

  // Time: O(nlog(n)), Space: O(n)
  public boolean isBalancedTreeTopDown(TreeNode root) {
    if (root == null) return true;
    return Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 &&
      isBalancedTreeTopDown(root.left) && isBalancedTreeTopDown(root.right);
  }

  // Time: O(n), Space: O(n)
  public boolean isBalancedTreeBottomUp(TreeNode root) {
    return getHeightAndCheck(root) != -1;
  }

  int getHeightAndCheck(TreeNode root) {
    if (root == null) return 0;

    int left = getHeightAndCheck(root.left);
    if (left == -1) return -1;

    int right = getHeightAndCheck(root.right);
    if (right == -1) return -1;

    if (Math.abs(left - right) > 1) return -1;
    return Math.max(left, right) + 1;
  }

}