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.
样例
Given binary tree A={3,9,20,#,#,15,7}, B={3,#,20,15,7}
A) 3 B) 3
/ \ \
9 20 20
/ \ / \
15 7 15 7
The binary tree A is a height-balanced binary tree, but B is not.
思路：
看了网上的解法，好多的递归算法，时间复杂度应该为O(n),Depth first Search 空间上会比下面的算法节省，但是，要考虑JVM的栈溢出问题了。
总结下，递归算法，考虑问题简洁明了，但是也存在两个问题，一是 递归栈溢出问题，二是，存在迭代计算问题，本例中为树，迭代为单项计算，所以不存在重复计算问题，但是如果是图，那么迭代的问题要慎重考虑了。
转换思路，a.将要递归的数据放到数据集合 b.使用map存储所有计算结果供以后计算用，时间复杂度O(2*n)
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: The root of binary tree.
* @return: True if this Binary tree is Balanced, or false.
*/
public boolean isBalanced(TreeNode root) {
if (root == null)
return true;
Queue<TreeNode> q = new LinkedList<TreeNode>();
Stack<TreeNode> s = new Stack<TreeNode>();
q.offer(root);
s.push(root);
while (!q.isEmpty()) {
TreeNode f = q.poll();
TreeNode l = f.left;
TreeNode r = f.right;
if (l != null) {
q.offer(l);
s.push(l);
}
if (r != null) {
q.offer(r);
s.push(r);
}
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
while (!s.isEmpty()) {
TreeNode c = s.pop();
int l = 0;
if(c.left!=null && map.get(c.left.val) != null)
l = map.get(c.left.val);
int r = 0;
if(c.right!=null && map.get(c.right.val) != null)
r = map.get(c.right.val);
if ((l - r) * (l - r) > 1)
return false;
map.put(c.val, l > r ? l + 1 : r + 1);
}
return true;
}
}