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 a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if (root == null) { return res; } int stepSum = root.val; List<Integer> child = new ArrayList<>(); child.add(stepSum); dfs(res, child, root, sum, stepSum); return res; } public void dfs(List<List<Integer>> res, List<Integer> child, TreeNode root, int sum, int stepSum) { if(root.left == null && root.right == null && stepSum == sum) { res.add(new ArrayList<Integer>(child)); return; } if(root.left != null) { child.add(root.left.val); dfs(res, child, root.left, sum, stepSum + root.left.val); child.remove(child.size() - 1); } if(root.right != null) { child.add(root.right.val); dfs(res, child, root.right, sum, stepSum + root.right.val); child.remove(child.size() - 1); } } }