题目描述

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

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

示例:
给定如下二叉树,以及目标和 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);
    }
}
pwrliang Algorithms, DFS, Tree ,

Leave a Reply

Your email address will not be published. Required fields are marked *