[leetcode] Balanced Binary Tree | 看一棵二叉树是否balanced

Posted by: lexigrey on: October 7, 2013

• In: classic | leetcode
• Leave a Comment

经典题，注意balanced的定义：左右子树都balance，且高度差<=1。所以下面这个也是balanced的，即使a的做右子树都不是完全树。

    a
   / \ 
  b   d
 /     \
c       e

唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”，直接用height = -1表示不平衡就行。

public boolean isBalanced(TreeNode root) {
  return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
  if (root == null)
    return 0;
  int leftHeight = getHeight(root.left);
  if (leftHeight < 0)
    return -1;
  int rightHeight = getHeight(root.right);
  if (rightHeight < 0)
    return -1;
  if (Math.abs(leftHeight - rightHeight) > 1)
    return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}

Advertisements

Tags: easy, tree, 后序