LeetCode 110. Balanced Binary Tree

Description

https://leetcode.com/problems/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]:

    3
   / \
  9  20
    /  \
   15   7

Return true.

Example 2:

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

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4

Return false.

Explanation

Create and use maxDepth() as a helper function. Check if the tree is balanced at the same time when we are calculating the max depth of the tree. If the tree is not balanced, use maxDepth() to return null as an indicator.

Video Tutorial

Java Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDepth(root) != null;        
    }
    
    private Integer maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Integer leftDepth = maxDepth(root.left);
        Integer rightDepth = maxDepth(root.right);
        
        if (leftDepth == null || rightDepth == null) {
            return null;
        }
        
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return null;
        }
        
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *