110. Balanced Binary Tree

发表于 | 分类于

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.

解法1：

按照定义，balanced是指left tree和right tree的max height的差值可以小于等于1，同时要满足left tree和right tree都是一个balanced tree。
用返回一个resultSet的办法返回多值，（balanced，maxHeight). 要注意的是返回的时候root的height需要是max(leftHeight, rightHeight) + 1
C++

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct resultSet {
    bool isBalanced;
    int maxHeight;
    resultSet(bool b, int h): isBalanced(b), maxHeight(h) {}
};
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        resultSet res = helper(root);
        return res.isBalanced;
    }
    resultSet helper(TreeNode* root) {
        if (root == NULL) {
            return resultSet(true, 0);
        }
        if (!root->left && !root->right) {
            return resultSet(true, 1);
        }
        resultSet left = helper(root->left);
        if (!left.isBalanced) {
            return resultSet(false, 0);
        }
        resultSet right = helper(root->right);
        if (!right.isBalanced) {
            return resultSet(false, 0);
        }
        return resultSet(abs(left.maxHeight - right.maxHeight) <= 1, max(left.maxHeight, right.maxHeight) + 1);
    }
};

Java

1

解法2: O(N), 不需要mark node

直接用一个返回值来区分是否是balanced binary tree。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isBalanced(TreeNode root) {
        return depth(root) != -1;
    }
    private int depth(TreeNode root) {
        if (root == null) return 0;
        int left = depth(root.left);
        if (left == -1) return -1;
        int right = depth(root.right);
        if (right == -1) return -1;
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}