BalancedBinaryTree [source code]

public class BalancedBinaryTree {
static
/******************************************************************************/
public class Solution {
    public boolean isBalanced(TreeNode root) {
        boolean[] accum = new boolean[1];
        accum[0] = true;
        dfs(root, 0, accum);
        return accum[0];
    }

    private int dfs(TreeNode root, int depth, boolean[] accum) {
        if (root == null) return depth;
        int left = dfs(root.left, depth + 1, accum);
        int right = dfs(root.right, depth + 1, accum);
        accum[0] = accum[0] && Math.abs(right - left) <= 1;
        return Math.max(left, right);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        BalancedBinaryTree.Solution tester = new BalancedBinaryTree.Solution();
    }
}

这题如果用 recursion 写是很简单的. 这个问题的算法如果想要加速, 我感觉用 iterative 写更好, 因为这个是一个check all类型的return boolean的问题, 如果写iterative, 可以使用premature exit;
不过实际上未必是这么回事, 因为 iterative 要使用各种结构, 这些结构的 overhead 可能造成最后的速度其实不如 recursion;

最后这个算法写起来也是比较简单, 速度是1ms (70%). 注意, 我这个写法实际上还不是最差的写法, 最差的写法是 isBalanced 也做成一个recursion, 这样最后就是两个 recursion, 这个速度就狗屎了;

Recursive Call argument: the Argument in the Call to the Node, is what the Node gets

如题, 这个问题也是另外一个题目里面讨论过一次的话题了; 有时候确实搞不清楚, 事实上, 无论你怎么记都无所谓, 只要稳定固定于某一种对应关系就行了. 这一种对应关系更容易记忆;

这个是 submission 上面另外一个解法, 不依赖于 accum 或者 global:

public class Solution {  
    public boolean isBalanced(TreeNode root) {  
        return maxDepth(root) != -1;  
    }  

    private int maxDepth(TreeNode root) {  
        if (root == null) {  
            return 0;  
        }  

        int left = maxDepth(root.left);  
        int right = maxDepth(root.right);  
        if (left == -1 || right == -1 || Math.abs(left-right) > 1) {  
            return -1;  
        }  
        return Math.max(left, right) + 1;  
    }  

}

因为只要你在某一个 node 返回了一个异常值, 你就可以把这个异常值一直上行返回上去, 这样最后结果就可以直接判断, 而不用借助于一个accum;

这个是 discussion 里面的一个观点:
Below is a representation of the tree input: {1,2,2,3,3,3,3,4,4,4,4,4,4,#,#,5,5}:

    ____1____  
   /         \  
  2           2  
 /  \        / \  
3    3      3   3  

/\ /\ /\
4 4 4 4 4 4
/\
5 5
好像确实是有道理的, 这个问题给出的 balanced 的定义确实有点问题; 如果最后当 tree 足够大, 这样的一个传一个的造成的 unbalance 会越来越严重;

看了一下, iterative DFS traversal实现起来好像有点复杂;
这个是 discussion 上一个人的做法:

public class Solution {  
    public boolean isBalanced(TreeNode root) {  
        if(root==null) return true;  
        Stack<TreeNode> stack = new Stack<TreeNode>();  
        Map<TreeNode, Integer> map = new HashMap<TreeNode, Integer>();  
        stack.push(root);  
        while(!stack.isEmpty()){  
            TreeNode node = stack.pop();  
            if((node.left==null || node.left!=null && map.containsKey(node.left)) &&(node.right==null || node.right!=null && map.containsKey(node.right))){  
                int left = node.left==null?0:map.get(node.left);  
                int right = node.right==null?0:map.get(node.right);  
                if(Math.abs(left-right) > 1) return false;  
                map.put(node, Math.max(left, right)+1);  
            }else{  
                if(node.left!=null && !map.containsKey(node.left)){  
                    stack.push(node);  
                    stack.push(node.left);  
                }else{  
                    stack.push(node);  
                    stack.push(node.right);  
                }  
            }  
        }  
        return true;  
    }  
}

还是有点复杂, 最后的速度比较差:12(3).
他这个做法其实是比较粗糙的, 就是用 Map 一个一个的记录;
TODO: 做一个不依赖map 的 iterative 解;

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.

Difficulty:Easy
Category:Algorithms
Acceptance:37.22%
Contributor: LeetCode
Companies
bloomberg
Related Topics
tree depth-first search
Similar Questions
Maximum Depth of Binary Tree