113 路径总和 II

本文最后更新于：2021年7月22日 晚上

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

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

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

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

返回:

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

**Solution **

参考 LeetCode官方

  • 深度优先搜索
  • 要遍历整个树，找到所有路径，「所以递归函数不要返回值！」
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    
    void dfs(TreeNode* root, int sum){
        if(root==nullptr) return ;
        path.emplace_back(root->val);
        sum -= root->val;

        if(root->left==nullptr && root->right==nullptr && sum==0){
            res.emplace_back(path);
        } else{
            if(root->left)
                dfs(root->left, sum);
            if(root->right)
                dfs(root->right, sum);
        }
        path.pop_back();
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        dfs(root, targetSum);
        return res;
    }
};
// @lc code=end

  • 广度优先遍历

  • 构建两个队列，分别存储节点 和 从根节点到当前节点的和。

  • 使用哈希表记录树中的每一个节点的父节点。每次找到一个满足条件的节点，就从该节点出发不断向父节点迭代，即可还原出从根节点到当前节点的路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public:
    vector<vector<int>> res;
    unordered_map<TreeNode*, TreeNode*> parent;

    void getPath(TreeNode* node){
        vector<int> path;
        while(node){
            path.emplace_back(node->val);
            node = parent[node];
        }
        reverse(path.begin(), path.end());
        res.emplace_back(path);
    }

    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr) return res;
        queue<TreeNode *> qNode;
        queue<int> qSum;

        qNode.push(root);
        qSum.push(root->val);

        while(!qNode.empty()){
            TreeNode* node = qNode.front();
            int sum = qSum.front();
            qNode.pop(); qSum.pop();

            if(node->left==nullptr && node->right==nullptr && sum==targetSum){
                getPath(node);
            } else {
                if(node->left){
                    parent[node->left]  = node;
                    qNode.emplace(node->left);
                    qSum.emplace(sum+node->left->val);
                }
                if(node->right){
                    parent[node->right]  = node;
                    qNode.emplace(node->right);
                    qSum.emplace(sum+node->right->val);
                }
            }
        }
        return res;
    }
};