https://leetcode-cn.com/problems/path-sum-ii/

image.png

（圖片來源https://leetcode-cn.com/problems/path-sum-ii/

）

遞歸

// 回溯
public class a_PathSum_2_113 {

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> solution = new ArrayList<>();

        findSum(res, solution, root, sum);

        return res;
    }

    private void findSum(List<List<Integer>> result, List<Integer> solution, TreeNode root, int residual){
        if (root == null) {
            return;
        }

        residual -= root.val;
        solution.add(root.val);
        // 這里有必要解釋下為什么不把這個(gè)條件和上一個(gè)條件合并
        // 以 root==null，且 residual == root.val 作為終點(diǎn)；
        // 因?yàn)檫@么寫，左右子樹會(huì)各來一遍，result會(huì)加入兩遍solution
        if (residual == 0 && root.left == null && root.right == null) {

            result.add(new ArrayList<>(solution));
        }

        findSum(result, solution, root.left, residual);
        findSum(result, solution, root.right, residual);
        solution.remove(solution.size()-1);
    }

}