Problem 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.

Solution:

  • bottom-up method:
    Instead of calling depth() explicitly for each child node, we return the height of the current node in DFS recursion. When the sub tree of the current node (inclusive) is balanced, the function dfsHeight() returns a non-negative value as the height. Otherwise -1 is returned. According to the leftHeight and rightHeight of the two children, the parent node could check if the sub tree
    is balanced, and decides its return value.

In this bottom up approach, each node in the tree only need to be accessed once. Thus the time complexity is O(N), better than the first solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check(root):
            if not root:
                return 0
            left = check(root.left)
            if left == -1: return -1
            right = check(root.right)
            if right == -1: return -1
            
            if abs(left-right) > 1: return -1
            return max(left, right) + 1
        return check(root) != -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class solution {
public:
int dfsHeight (TreeNode *root) {
        if (root == NULL) return 0;
        
        int leftHeight = dfsHeight (root -> left);
        if (leftHeight == -1) return -1;
        int rightHeight = dfsHeight (root -> right);
        if (rightHeight == -1) return -1;
        
        if (abs(leftHeight - rightHeight) > 1)  return -1;
        return max (leftHeight, rightHeight) + 1;
    }
    bool isBalanced(TreeNode *root) {
        return dfsHeight (root) != -1;
    }
};

time complexity: O(n)

  • top-down solution
    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
    /**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
    class Solution {
    public:
        int depth (TreeNode *root) {
            if (root == NULL) return 0;
            return max (depth(root -> left), depth (root -> right)) + 1;
        }

        bool isBalanced (TreeNode *root) {
            if (root == NULL) return true;
            
            int left= depth(root->left);
            int right= depth(root->right);
            
            return abs(left - right) <= 1 && isBalanced(root->left) && isBalanced(root->right);
        }
    };

time complexity: O(N^2) for worst case

reference:
https://goo.gl/25GVKA