Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

    Note: A leaf is a node with no children.

    Example:

    Given the below binary tree and sum = 22,

    1.             5
    2.      / \
    3.     4   8
    4.    /   / \
    5.   11  13  4
    6.  /  \    / \
    7. 7    2  5   1

    Return:

    1. [
    2.    [5,4,11,2],
    3.    [5,8,4,5]
    4. ]

    题意

    判断给定树中是否存在这样一条从根到叶的路径，使得路径上的数字之和等于目标值。记录下所有这样的路径。

    思路

    在 112. Path Sum 的基础上，保存所有符合条件的路径。依然是回溯法。

    代码实现

    1. /**
    2.  * Definition for a binary tree node.
    3.  * public class TreeNode {
    4.  *     int val;
    5.  *     TreeNode left;
    6.  *     TreeNode right;
    7.  *     TreeNode(int x) { val = x; }
    8.  * }
    9.  */
    10. class Solution {
    11.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
    12.         List<List<Integer>> ans = new ArrayList<>();
    13.         pathSum(root, 0, sum, new ArrayList<>(), ans);
    14.         return ans;
    15.     }
    17.     private void pathSum(TreeNode x, int preSum, int sum, List<Integer> list, List<List<Integer>> ans) {
    18.         if (x == null) {
    19.             return;
    20.         }
    22.         list.add(x.val);
    23.         if (preSum + x.val == sum && x.left == null && x.right == null) {
    24.             ans.add(new ArrayList<>(list));
    25.         } else {
    26.             pathSum(x.left, preSum + x.val, sum, list, ans);
    27.             pathSum(x.right, preSum + x.val, sum, list, ans);
    28.         }
    29.         list.remove(list.size() - 1);
    30.     }
    31. }