113-路径总和 II

马谦马谦马谦

615
文章

17
评论

2018 年 12 月 14 日 17:56:54数据结构和算法评论624字数 590阅读 1 分 58 秒阅读模式

来源：力扣（LeetCode）

链接：113. 路径总和 II

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

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

示例:

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

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

/ \

4 8

/ / \

11 13 4

/ \ / \

7 2 5 1

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

[

[5,4,11,2],

[5,8,4,5]

]

二、题解

说明：

此题是112. 路径总和Ⅰ的升级版（题解参考：113-路径总和Ⅰ），相对于第一题来说，有以下两点不通：

题Ⅰ只需要判断存在即可，该题需要找到所有可能的结果。
找到所有结果的同时，该题还需要保存所有的路径。

算法：

递归+深搜遍历所有的树节点，每遍历一个节点除了计算 sum 是否满足条件以外，还要记录下该节点。当遇到满足条件的叶节点，把当前路径加到结果中去。需要利用到两个辅助的数组。

代码：

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        dfs(root, sum);
        return m_ans;
    }
private:
    void dfs(TreeNode *root, int sum) {
        if(root == NULL) {
            return;
        }

        // 节点添加到临时的数组里面去
        m_vec.push_back(root->val);
        sum -= root->val;

        if (root->left == NULL && root->right == NULL && sum == 0) {
            // 当前临时数组加入到结果数组中
            m_ans.push_back(m_vec);
        }

        // 遍历左节点
        if (root->left) {
            dfs(root->left, sum);
        }
		
        // 遍历右节点
        if (root->right) {
            dfs(root->right, sum);
        }
        
        // 最关键的一步：回溯状态
        // 函数入口处把当前节点添加到临时数组里面去了，这里退出的时候要删掉这一个节点
        // 避免当前节点还存在于临时数组中，影响后续的遍历结果
        m_vec.pop_back();
    }

    vector<vector<int>> m_ans; // 保存所有的结果
    vector<int> m_vec; // 临时保存路径的数组
};