Question

link

Stats

Frequency	2
Difficulty	1
Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question for me.

My first code contains many dulicate calls. I have posted it below as an illustration of bad example.

Solution

The solution should make use of the return value from the recursion, and avoid duplication calls. The standard solution is posted below.

Code

First, my initial solution. It takes 30ms more than next code.

public boolean isBalanced(TreeNode root) {
    // my old code re-submit, for speed test
    if (root == null) return true;
    if (Math.abs(depth(root.left) - depth(root.right)) > 1) {
        return false;
    }
    if (! isBalanced(root.left)) return false;
    if (! isBalanced(root.right)) return false;
    return true;
}

private int depth(TreeNode node) {
    if (node == null) return 0;
    if (node.left == null) return 1 + depth(node.right);
    if (node.right == null) return 1 + depth(node.left);
    return 1 + Math.max(depth(node.left), depth(node.right));
}

Second, the standard solution

public boolean isBalanced(TreeNode root) {
    return helper(root) != -1;
}

private int helper(TreeNode node) {
    if (node == null) return 0;
    int a = helper(node.left);
    if (a == -1) return -1;
    int b = helper(node.right);
    if (b == -1) return -1;
    if (Math.abs(a - b) <= 1) 
        return Math.max(a, b) + 1;
    else return -1;
}