Time = O(n): 遍历树中的每一个节点一次
Space = O(n)
/**
* 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<>();
if (root == null) {
return res;
}
List<Integer> cur = new ArrayList<>();
pathSumHelper(root, sum, cur, res);
return res;
}
private void pathSumHelper(TreeNode root, int sum, List<Integer> cur, List<List<Integer>> res) {
if (root == null) {
return;
}
cur.add(root.val);
if (root.left == null && root.right == null) {
if (root.val == sum) {
res.add(new ArrayList<>(cur));
}
}
pathSumHelper(root.left, sum - root.val, cur, res);
pathSumHelper(root.right, sum - root.val, cur, res);
cur.remove(cur.size() - 1);
}
}