题目描述

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

返回:

[
   [5,4,11,2],
   [5,8,4,5]
]

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

解法1

这道题是“112. 路径总和”的升级版本，在这道题我们需要把所有可能的解都存储下来并返回。为了记录路过的节点，我们使用一个变量List<Integer> path来存储路过的节点的值。我们将每个路过的节点的值都放入path中，如果走到叶节点发现是一条可行的路径（节点值之和等于sum），我们就复制path数组，然后放入到结果变量List<List<Integer>> ans。当从节点返回时，我们需要回溯以保证path变量的正确性。

上面的思路可以使用二叉树的先序遍历来实现。我们用题目给的case来描述执行过程：我们不断地向左走，找到一条路径”5->4->11->7″，path变量的内容依次变为[5], [5, 4], [5, 4, 11], [5, 4, 11, 7]。然后我们发现这条路径的和不等与sum，我们从节点7回溯，path变量从[5,4,11,7]变为[5,4,11]，回到节点11走向它的右子树，此时path变量为[5,4,11,2]，发现路径和与sum相等，复制path数组的到ans。因为我们需要复用path数组，所以不能直接调用ans.add(path)，而是应该调用ans.add(new ArrayList<>(path))，创建path的副本并加入到ans中。

假设我们不考虑path数组复制的过程，那么时间复杂度为O(n)（因为要遍历所有节点），空间复杂度为O(n)（空间为调用栈开销）。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> ans = new ArrayList<>();

        helper(root, sum, ans, new ArrayList<>());

        return ans;
    }

    private void helper(TreeNode node, int sum, List<List<Integer>> ans, List<Integer> path) {
        if (node == null) {
            return;
        }

        // 将沿途到节点加入到path中
        sum -= node.val;
        path.add(node.val);

        // 遍历到叶节点
        if (node.left == null && node.right == null) {
            // 如果这是一条可行的路径，才复制path的结果到ans
            if (sum == 0)
                ans.add(new ArrayList<>(path));
        } else {
            helper(node.left, sum, ans, path);
            helper(node.right, sum, ans, path);
        }

        // 回溯
        path.remove(path.size() - 1);
    }
}