判断二叉树是否平衡

判断二叉树是否平衡

问题

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

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

     1
   /   \
  2     4
       / \
      8  16

它的任意节点的左右子树高度差都不大于 1，因此它是一棵平衡二叉树。

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

     1
   /   \
  2     4
         \
          8
           \
           16

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

     1
   /   \
  2     4
       / \
      8  16

它的逆层序遍历结果是：

[
 [8, 16]，
 [2, 4],
 [1],
]

代码

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

}