Leetcode(110) Balanced Binary Tree

发表于 | 分类于

Description

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example 1:

Given the following tree [3,9,20,null,null,15,7]:

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

Return true.

Example 2:

Given the following tree [1,2,2,3,3,null,null,4,4]:

1
2
3
4
5
6
7
      1
     / \
    2   2
   / \
  3   3
 / \
4   4

Return false.

解法

递归地求解树的高度，同时如果发现了左右子树高度差大于1的情况，直接返回高度为-1代表不平衡，节省计算时间。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        int left = height(root.left);
        int right = height(root.right);
        if (left == -1 || right == -1)
            return false;
        if (Math.abs(left - right) <= 1) {
            return true;
        }
        return false;
    }

    Integer height(TreeNode root) {
        if (root == null)
            return 0;
        int left = height(root.left);
        int right = height(root.right);
        if (left == -1 || right == -1)
            return -1;
        if (Math.abs(left - right) <= 1)
            return Math.max(left, right) + 1;
        else
            return -1;
    }
}