/**
 * 
 */
package com.wangsus.codetest.difficulty1;

import com.wangsus.codetest.datastructure.TreeNode;

/**
 * @author Su
 *
 *
 *Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
 */
public class Path_Sum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}
	/**
	 * Definition for binary tree
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */
	public class Solution {
	    public boolean hasPathSum(TreeNode root, int sum) {
	        return false;
	    }
	}
}

@@ -1,16 +1,4 @@
-/**%0A * %0A */%0A
 pack
@@ -36,16 +36,68 @@
 ulty1;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.List;%0A%0A
 import c
@@ -921,16 +921,16 @@
 ution %7B%0A
-
 %09    pub
@@ -978,16 +978,1037 @@
  sum) %7B%0A
+%09    %09//try depth first search%0A%09    %09List%3CTreeNode%3E dfs = new ArrayList%3CTreeNode%3E();%0A%09    %09List%3CInteger%3E cSum = new ArrayList%3CInteger%3E();%0A%09    %09if(root==null)%7B%0A%09    %09%09return false;%0A%09    %09%7D%0A%09    %09if(root.val==sum&&root.left==null&&root.right==null)%7B%0A%09    %09%09return true;%0A%09    %09%7D%0A%09    %09if(root.left!=null)%7B%0A%09    %09%09dfs.add(root.left);%0A%09    %09%09cSum.add(root.val+root.left.val);%0A%09    %09%7D%0A%09    %09if(root.right!=null)%7B%0A%09    %09%09dfs.add(root.right);%0A%09    %09%09cSum.add(root.val+root.right.val);%0A%09    %09%7D%0A%09    %09while(!dfs.isEmpty())%7B%0A%09    %09%09TreeNode current = dfs.get(0);%09    %09%09%0A%09    %09%09int currentSum = cSum.get(0);%0A%09    %09%09dfs.remove(0);%0A%09    %09%09cSum.remove(0);%0A%09    %09%09if(current.left==null&&current.right==null)%7B%0A%09    %09%09%09if(currentSum==sum)%7B%0A%09    %09%09%09%09return true;%0A%09    %09%09%09%7D%0A%09    %09%09%7D%0A%09    %09%09if(current.left!=null)%7B%0A%09%09    %09%09dfs.add(0,current.left);%0A%09%09    %09%09cSum.add(0,current.val+current.left.val);%0A%09%09    %09%7D%0A%09%09    %09if(current.right!=null)%7B%0A%09%09    %09%09dfs.add(0,current.right);%0A%09%09    %09%09cSum.add(0,current.val+current.right.val);%0A%09%09    %09%7D%0A%09    %09%7D%0A
 %09       

Path_Sum Wrong