Balanced Binary Tree

Posted on Edited on In Views:

110.Balanced Binary Tree

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

Example 1:

img

1
2
Input: root = [3,9,20,null,null,15,7]
Output: true

Example 2:

img

1
2
Input: root = [1,2,2,3,3,null,null,4,4]
Output: false

Example 3:

1
2
Input: root = []
Output: true

时间复杂度：O(n)
空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return height(root) >= 0;
    }
    int height(TreeNode* root) {
        if (root == nullptr)return 0;
        int left_height = height(root->left);
        int right_height = height(root->right);
        if (left_height == -1 || right_height == -1 || abs(left_height - right_height) > 1) {
            return -1;
        }
        else {
            return max(left_height, right_height) + 1;
        }
    }
};