[4.8] any path sum

1. Example


All Path and find out which path has a sum,

http://algorithms.tutorialhorizon.com/files/2014/11/Maximum-Sum-path-between-two-leaves.png


-5->4 ->11 -2 -8  7 12==>  sum(20) -12-7+8+2-11 = 0




helper(root,  List<Integer> )
list.add(root.val)
//** check every path so far, are they a sum, by minus all the previous node to check 

we look “up” to see if we’ve found the sum.“does this node complete a path with the sum?”

helper(root.left,           new List<Integer>(list) )
helper(root.right,     new List<Integer>(list) )

http://codercareer.blogspot.com/2011/09/no-04-paths-with-specified-sum-in.html



Figure 1: A binary tree with two paths where the sum of all nodes value is 22: 

One is the path contains node 10 and 12, 

and the other contains node 10, 5 and 7

2. Implementation

// Time:O(n log n)
// 2^r nodes at level r
// ever level every node

// n node, and for each node loop up take O(logn)

void findSum(TreeNode root, int sum, List list, int start)
{


        // Base case
        if ( root ==null )
            return;
        int tmp = sum;



        list.add(root.val);




        
        for (int stop = start; stop >=0; stop--)
        {
             tmp = list.get(i);
             if (tmp == 0)
                 print(list, start, stop);
        }


        findSum(root.left, sum, new List(list), start+1);
        findSum(root.right, sum, new List(list), start+1);

}

void print(Lsit lsit, int start, int stop)
{
      for (int i = start; i <= stop;i++)
      {
               System.out.print(list.get(i)+" ");
      }
      System.out.println();
}

3. Similar ones
http://karmaandcoding.blogspot.com/2012/11/binary-search-tree-any-path-sum.html