[LeetCode 113] Path Sum II

题目链接：path-sum-ii

import java.util.ArrayList;
import java.util.List;


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

public class PathSumII {

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

//	114 / 114 test cases passed.
//	Status: Accepted
//	Runtime: 265 ms
//	Submitted: 0 minutes ago

	
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new ArrayList<List<Integer>>();
        dfs(root, paths, new ArrayList<Integer>(), sum);
        return paths;
        
    }
    public void dfs(TreeNode root, List<List<Integer>> paths, List<Integer> path, int sum) {
    	if(root == null) return;
    	if(root.left == null && root.right == null) {
    			if(sum == root.val) {
    				List<Integer> newPath = new ArrayList<Integer>(path);
    				newPath.add(root.val);
    				paths.add(newPath);
    			}
    		return;
    	}

    	if(root.left != null) {
    		List<Integer> newPath = new ArrayList<Integer>(path);
			newPath.add(root.val);
    		dfs(root.left, paths, newPath, sum - root.val);
    	}
    	
    	if(root.right != null) {
    		List<Integer> newPath = new ArrayList<Integer>(path);
			newPath.add(root.val);
    		dfs(root.right, paths, newPath, sum - root.val);
    	}    	
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}

[LeetCode 113] Path Sum II

原文：http://blog.csdn.net/ever223/article/details/44559209