[leetcode]Path Sum II

新博文地址：[leetcode]Path Sum II

Path Sum II 

 

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]
]

 跟上一道并无太差差别，如果有指向父节点的指针代码会比较好看点，总之差别并不大

	ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
	 public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
		if(root == null || (root.left == null && root.right == null && root.val != sum)){
			return result;
		}
		ArrayList<Integer> list = new ArrayList<Integer>();
		list.add(root.val);
		dfs(root,sum,list);
		return result;
	}
	
	private void dfs(TreeNode root,int sum,ArrayList<Integer> preList){
		if(root == null || (root.left == null && root.right == null && root.val != sum)){
			return;
		}else if(root.left == null && root.right == null && root.val == sum){
			result.add(preList);
		}else{
			if(root.left != null){
				ArrayList<Integer> leftPath = getPrePath(preList,root.left.val);
				dfs(root.left ,sum - root.val,leftPath);
			}
			if(root.right != null){
				ArrayList<Integer> rightPath = getPrePath(preList, root.right.val);
				dfs(root.right ,sum - root.val,rightPath);
			}
		}
	}
	
	private ArrayList<Integer> getPrePath(List<Integer> preList,int val){
		ArrayList<Integer> result = new ArrayList<Integer>(preList);
		result.add(val);
		return result;
	}