LeetCode 113 路经总和II

LeetCode 113 路经总和II

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

DFS+回溯

执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：39.6 MB, 在所有 Java 提交中击败了10.71%的用户

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        //根节点到叶子节点路径和为给定值的路径总数
        List<List<Integer>> results = new ArrayList<>();
        backtrace(root, 0, sum, new ArrayList<Integer>(), results);

        return results;
    }

    public void backtrace(TreeNode root, int currSum, int target, List<Integer> currPath, List<List<Integer>> paths) {
        if(root==null) {
            return;
        }
        //满足条件的根节点处终止并添加到结果集合
        else if(root.left==null && root.right==null && currSum==target-root.val) {
            currPath.add(root.val);
            paths.add(new ArrayList<Integer>(currPath));
            currPath.remove(currPath.size()-1);
            return;
        }
        
        //继续向下深度遍历
        currPath.add(root.val);
        currSum += root.val;
        backtrace(root.left, currSum, target, currPath, paths);
        backtrace(root.right, currSum, target, currPath, paths);
        //回溯
        currPath.remove(currPath.size()-1);

        return;
    }
}