Leetcode–Balanced Binary Tree

The Problem:

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.

Notes:

  1. This problem can be tackled by examine left and right subtree balance of each node recursively. If either subtree is not balanced, or length difference of two subtrees is greater than 1, then return false.
  2. Recursion function should return the height of subtree, and we can use a flag of -1 to indicate an unbalanced subtree.

Java Solution

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s