Tree Node With Subtree Sum - Facebook

http://www.1point3acres.com/bbs/thread-127924-1-1.html
第二题有点像，给一个tree，返回每个点左右子树的和与自己值的差，用递归做，还问了不递归怎么做

1.         public static ArrayList<Integer> treeNodeWithSubtreeSum(TreeNode root) {. 1point 3acres 璁哄潧
2.                 ArrayList<Integer> ret = new ArrayList<Integer>();
3.                 if (root == null). 1point 3acres 璁哄潧
4.                         return ret;.鏈枃鍘熷垱鑷�1point3acres璁哄潧
5.                 Stack<TreeNode> s = new Stack<TreeNode>();
6.                 HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
7.                 s.add(root);
8.                 TreeNode pre = null;. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
9.                 while (!s.isEmpty()) {
10.                         TreeNode cur = s.peek();
11.                         if (pre == null || pre.left == cur || pre.right == cur) {
12.                                 if (cur.left != null) {
13.                                         s.push(cur.left);
14.                                 } else if (cur.right != null) {
15.                                         s.push(cur.right);
16.                                 } else {
17.                                         s.pop();
18.                                         map.put(cur.val, 0);. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
19.                                         ret.add(cur.val - map.get(cur.val));
20.                                 }
21.                         } else if (cur.left == pre) {
22.                                 if (cur.right != null) {
23.                                         map.put(cur.val, map.get(pre.val) + pre.val);
24.                                         s.push(cur.right);
25.                                 } else {.1point3acres缃�
26.                                         s.pop();
27.                                         map.put(cur.val, map.get(pre.val) + pre.val);
28.                                         ret.add(cur.val - map.get(cur.val));
29.                                 }
30.                         } else if (cur.right == pre) {
31.                                 s.pop();
32.                                 int tmp = 0;
33.                                 if (map.containsKey(cur.val))
34.                                         tmp = map.get(cur.val);
35.                                 tmp += map.get(pre.val) + pre.val;
36.                                 map.put(cur.val, tmp);
37.                                 ret.add(cur.val - map.get(cur.val));
38.                         }
39.                         pre = cur;
40.                 }. From 1point 3acres bbs
41.                 return ret;
42.         }