Balanced Binary Tree

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