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 left and right subtrees of every node differ in height by no more than 1.

Example 1: alt

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

Example 2: alt

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

Example 3:

Input: root = []
Output: true

Solution 1: O(nlogn)¶

// O(nlogn)
class Solution {
Solution 1: O(nlogn)
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
        int left_height = height(root->left);
        int right_height = height(root->right);
        return (abs(left_height - right_height)<=1) && isBalanced(root->left) && isBalanced(root->right);
    }
private:
    int height(TreeNode* root) {
        if(!root) return 0;
        return max(height(root->left), height(root->right))+1;
    }
};

Solution 2: O(n)¶

// Running time: 1 ms
class Solution {
  private boolean balanced;

  private int height(TreeNode root) {
    if (root == null || !this.balanced) return -1;
    int l = height(root.left);
    int r = height(root.right);
    if (Math.abs(l - r) > 1) {
      this.balanced = false;
      return -1;
    }
    return Math.max(l, r) + 1;
  }

  public boolean isBalanced(TreeNode root) {
    this.balanced = true;
    height(root);
    return this.balanced;
  }
}