[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 1return[[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 agopublic 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}}

，世上最累人的事，莫过於虚伪的过日子