题解参考

本题同 剑指 Offer 34. 二叉树中和为某一值的路径

问题

分析

1. 节点值可能有正有负，必须dfs把能走的节点都走一遍；
2. 一定是从根节点到叶子结点，考虑输入为：[1,2] 1，输出为：[] 的情况；

在具体编写代码的时候要考虑的问题：

1. 什么时候回溯？

   • 对于一般的dfs，在左右递归之后，要回溯，把当前节点从path中删除；

   • 如果在一定条件下可以提前return，在if语句里不要忘了回溯；

2. sum在什么时候更新？

   • 在当前层直接更新然后做sum == 0 的判断 ✅
   • 在当前层做sum == root.val 的判断，然后再递归传参时sum - root.val ✅

// 1ms 39.3MB
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null){return Collections.emptyList();}
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> path = new ArrayList<>();
        backtrack(root, sum, path, res);
        return res;
    }
    private void backtrack(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res){
        if (root == null){
            return ;
        }
        path.add(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0){
            res.add(new ArrayList<>(path));
        }
        backtrack(root.left, sum, path, res);
        backtrack(root.right, sum, path, res);
        path.remove(path.size() - 1);
    }
}

// 1ms 39.2MB
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null){return Collections.emptyList();} // 返回一个空列表
        List<List<Integer>> res = new ArrayList<List<Integer>>(); 
        List<Integer> path = new ArrayList<>();
        backtrack(root, sum, path, res);
        return res;
    }
    private void backtrack(TreeNode root, int sum, List<Integer> path, List<List<Integer>> res){
        if (root == null){ // dfs的出口
            return ;
        }
        path.add(root.val);
        sum -= root.val; 
        if (root.left == null && root.right == null){
            if (sum == 0){
                res.add(new ArrayList<>(path));
            }
            path.remove(path.size() - 1); // 代码的优雅性差些 
            return ; //提前返回，可以节省继续dfs的空间开销
        }
        backtrack(root.left, sum, path, res);
        backtrack(root.right, sum, path, res);
        path.remove(path.size() - 1);
    }
}

一些tricks：

1. 要尽量修改sum，使递归的出口为sum == 0，这样可以不用引入额外的变量；
2. 为提升代码的优雅性，dfs 左右孩子的时候不需要判断左右孩子是否存在，因为进入下一层递归时，会有root是否存在的判断（出口）；

// 没使用tricks的代码
// 2ms 39.3MB
class Solution {
    /*    res本身就是一个引用型变量，
   	只有在pathSum函数调用backtrack的时候会对其进行修改，
    因此定义在pathSum函数里就可以了，没必要在全局声明。*/
    List<List<Integer>> res = new ArrayList<List<Integer>>(); 
    int pathSumVal = 0;
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null){return Collections.emptyList();}
        List<Integer> path = new ArrayList<>();
        backtrack(root, sum, path);
        return res;
    }
    private void backtrack(TreeNode root, int sum, List<Integer> path){
        if (root == null){
            return ;
        }
        path.add(root.val);
        pathSumVal += root.val; // 要善于在sum上直接进行修改，省去引入新变量消耗的资源。
        if (pathSumVal == sum && root.left == null && root.right == null){
            res.add(new ArrayList<Integer>(path));
        } else{
            /*要规避这种冗余代码的书写*/			
            if (root.left != null){
                backtrack(root.left, sum, path);
                pathSumVal -= path.get(path.size() - 1);
                path.remove(path.size() - 1);
            }
            if (root.right != null){
                backtrack(root.right, sum, path);
                pathSumVal -= path.get(path.size() - 1);
                path.remove(path.size() - 1);
            }
        } 
    }
}