Path Sum II (Java)

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

Solution:  DFS

Apply DFS check every possible combination, record result if meet requirement

	Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
	For example:
	Given the below binary tree and sum = 22,
	5
	/ \
	4 8
	/ / \
	11 13 4
	/ \ / \
	7 2 5 1
	return
	[
	[5,4,11,2],
	[5,8,4,5]
	]
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// code rewrite 2/21
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	if (root==null){
	return result;
	}
	ArrayList<Integer> current=new ArrayList<Integer>();
	buildResult(root, sum, current, result);
	return result;
	}
	private void buildResult(TreeNode root,int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result){
	if (root==null){
	return;
	}
	int currentVal=root.val;
	current.add(currentVal);
	if (root.left==null && root.right==null){
	if (sum-currentVal==0){
	ArrayList<Integer> temp=new ArrayList<Integer> (current);
	result.add(temp);
	}
	}
	buildResult(root.left, sum-currentVal, current, result);
	buildResult(root.right, sum-currentVal, current, result);
	current.remove(current.size()-1);
	}
	}
	public class Solution {
	public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList <Integer> current=new ArrayList<Integer>();
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	pathSumHelper(root, sum, current, result);
	return result;
	}
	public void pathSumHelper
	(TreeNode root, int sum, ArrayList<Integer> current, ArrayList<ArrayList<Integer>> result)
	{
	if (root==null){
	return;
	}
	current.add(root.val);
	int current_sum=sum-root.val;
	if (current_sum==0&& root.left==null && root.right==null){
	ArrayList<Integer> temp=new ArrayList<Integer>();
	for(int i:current){
	temp.add(i);
	}
	result.add(temp);
	}
	pathSumHelper(root.left, current_sum, current, result);
	pathSumHelper(root.right, current_sum, current, result);
	current.remove(current.size()-1);
	}
	}

view raw Path Sum II.java hosted with ❤ by GitHub