题解 | #二叉树根节点到叶子节点和为指定值的路径#

题目描述

给定一个二叉树和一个值 sum，请找出所有的根节点到叶子节点的节点值之和等于 sum 的路径，
例如：
给出如下的二叉树，sum=22，

返回[[5,4,11,2],[5,8,9]]

题目分析

遍历树的所有路径，统计路径和，若有路径和与指定值相等，则将路径记录下来。题目的示例中有两条路径的和是符合条件的[[5,4,11,2],[5,8,9]]。

解题思路

使用dfs遍历树
要点：
1.在dfs的过程中，使用List类型的path记录走过的结点值, List类型res记录满足条件的路径path；
2.使用sum记录path的结点值和；
3.当遍历到叶子结点时，判断当前和满足条件，满足则加入res中；
4.返回上一结点时，path需要减掉当前结点的值；

代码实现

Java实现

    // 记录结果
    public ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> pathSum (TreeNode root, int sum) {
        // write code here
        dfs(root, sum, new ArrayList<Integer>());
        return res;
    }
    public void dfs(TreeNode root, int sum, ArrayList<Integer> list){
        if(root == null) return;
        // 减去当前结点值
        sum -= root.val;
        // 记录当前结点值
        list.add(root.val);
        if(root.left == null && root.right == null && sum == 0){
            // 若是叶子结点，且路径和恰好等于目标值，则加入结果中
            res.add(new ArrayList<Integer>(list));
        }else{
            // 否则就继续遍历
            dfs(root.left, sum, list);
            dfs(root.right, sum, list);
        }
        // 返回上一结点时，需要将当前加入的结点值去掉
        if(list.size()>0) list.remove(list.size()-1);
    }

时间复杂度：O(n)，n是树的结点数，需要遍历整个树，时间复杂度为O(n)；
空间复杂度：O(n)，递归深度最大为n，空间复杂度为O(n)；

C++实现

    vector<vector<int>> res;
    vector<vector<int> > pathSum(TreeNode* root, int sum) {
        // write code here
        if (!root) return res;
        vector<int> path;
        dfs(root, path, sum);
        return res;
    }

    void dfs(TreeNode* root, vector<int> path, int sum) {
        if (!root) return;
        // 减去当前结点值
        sum = sum - root->val;
        // 记录当前结点值
        path.push_back(root->val);
        if (!root->left && !root->right && sum == 0){
            // 若是叶子结点，且路径和恰好等于目标值，则加入结果中
            res.push_back(path);
        }else{
            // 否则就继续遍历
            dfs(root->left, path, sum);
            dfs(root->right, path, sum);
        }
        // 返回上一结点时，需要将当前加入的结点值去掉
        path.pop_back();
    }

复杂度与Java实现一致