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 depth of the two subtrees of every node never differ by more than 1.

Naive Way: 一开始想到的还是一个recursive的方法，求出两边的height，然后一旦有不符合的就返回false。

算法复杂度O(n), space O(n)。

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

以上做法是一个postorder traversal 的做法，所以应该可以写成对应的iterative的形式。

算法复杂度O(n), space O(n)。

 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;  
   }  
 }  

Improved Way: 看到一个人用return -1来消去全局变量的做法，实在高明。
来自 pavel-shlyk

 public boolean isBalanced(TreeNode root) {  
   return root == null || balance(root, 1) > 0;  
 }  
 private int balance(TreeNode node, int level) {  
   int l = node.left != null ? balance(node.left, level+1) : level;  
   int r = node.right != null ? balance(node.right, level+1) : level;  
   if (l == -1 || r == -1 || Math.abs(r - l) > 1) return -1;  
   return Math.max(l, r);  
 }