437. Path Sum III

题目：

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  
    5   -3
   /     
  3   2   11
 /    
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

链接：https://leetcode.com/problems/path-sum-iii/#/description

3/25/2017

这道题自己想出来了思路，然而不会写后序遍历。。。

出现的问题：

1. 不会写iterative的后序遍历：（

2. Vector不好用，以后刷题也不用了。

3. 对几种主要的Collections的方法不熟悉

思路：后序遍历iterative时stack含有从根节点到当前节点的路径。我们用arraylist取代stack，每当有新元素加到stack时从尾到头看和是否为target，是的话＋1。一个stack可能有多个符合要求的路径（比如某节点值为0，或几个节点和为0）

performance 23ms，但是我认为这个应该算是中等题，简单题有点为难我了。

时间复杂度O(nlgn)，worst caseO(n^2)

 1 /**
 2  * Definition for a binary tree node.
 3  * public class TreeNode {
 4  *     int val;
 5  *     TreeNode left;
 6  *     TreeNode right;
 7  *     TreeNode(int x) { val = x; }
 8  * }
 9  */
10 public class Solution {
11     public int pathSum(TreeNode root, int sum) {
12         ArrayList<TreeNode> v = new ArrayList<TreeNode>();
13         if (root == null) return 0;
14         TreeNode prev = null; // previously traversed node
15         TreeNode curr = root;
16         int count =0;
17 
18         v.add(root);
19         if (root.val == sum) count++;
20         
21         while (!v.isEmpty()) {
22             curr = v.get(v.size()-1);
23             if (prev == null || prev.left == curr || prev.right == curr) { // traverse down the tree
24                 if (curr.left != null) {
25                     v.add(curr.left);
26                     count += getCurrentCount(v, sum);
27                 } else if (curr.right != null) {
28                     v.add(curr.right);
29                     count += getCurrentCount(v, sum);
30                 }
31             } else if (curr.left == prev) { // traverse up the tree from the left
32                 if (curr.right != null) {
33                     v.add(curr.right);
34                     count += getCurrentCount(v, sum);
35                 }
36             } else { // traverse up the tree from the right
37                 v.remove(v.size()-1);
38             }
39             prev = curr;
40         }
41         return count;
42     }
43     
44     private int getCurrentCount(ArrayList<TreeNode> v, int sum) {
45         int count = 0;
46         int tempSum = 0;
47         for (int i = v.size() - 1; i >= 0; i--) {
48             tempSum += v.get(i).val;
49             if (tempSum == sum) count++;
50         }
51         return count;
52     }
53 }

别人用hashmap储存prefix sum，我还没有看懂：

https://discuss.leetcode.com/topic/64526/17-ms-o-n-java-prefix-sum-method/11

更简单的recursive写法：

https://discuss.leetcode.com/topic/64388/simple-ac-java-solution-dfs