437 路径总和 III

本文最后更新于：2021年1月26日 下午

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

返回 3。和等于 8 的路径有:

1.  5 -> 3
2.  5 -> 2 -> 1
3.  -3 -> 11

Solution

参考 @ts13go 的解题思路

  • 深度优先搜索
  • 双递归，先序遍历，把每个遍历到的节点当作root（起点）进行搜索
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
// @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:
    int pathSum(TreeNode* root, int sum) {
        if(root==nullptr) return 0;
        return findPath(root, sum)+pathSum(root->left, sum)
                +pathSum(root->right, sum);
    }

    // 寻找包含 node 根结点，和为 sum 的路径个数
    int findPath(TreeNode* node, int sum){
        if(node==nullptr) return 0;
        int res=0;
        if(node->val==sum)
            res += 1;
        res += findPath(node->left, sum-node->val);
        res += findPath(node->right, sum-node->val);
        return res;
    }
};
// @lc code=end
  • 单递归，把每个遍历到的节点当作终点（路径必须包含终点），记录根到终点的路径，从路径往前搜索。
  • 递归栈会保存每次递归的变量，所以可以用一个vector来保存路径，每次递归的过程都取相应的路径，因此递归返回后，要进行弹出。
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
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        vector<int> path;
        return findPath(root, sum, path);
    }

    // 寻找包含 node 为终点，和为 sum 的路径个数
    int findPath(TreeNode* node, int sum, vector<int>& path){
        if(node==nullptr) return 0;
        int res=0;
        path.push_back(node->val);
        
        int curSum = 0;
        for(int i=path.size()-1; i>=0; --i){
            curSum += path[i];
            if(curSum==sum)
                res += 1;
        }

        res += findPath(node->left, sum, path);
        res += findPath(node->right, sum, path);
        path.pop_back();
        return res;
    }
};
  • 前缀和
  • 用一个hash表记录当前路径的前缀和出现的次数，每次寻找current_sum - sum存在的次数就可。
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
class Solution {
public:
    unordered_map<int,int> m;
    int res = 0, sum;

    int pathSum(TreeNode* root, int sum) {
        if(root==nullptr) return 0;
        this->sum = sum;
        // 构建前缀和
        m[0] = 1;
        dfs(root, root->val);

        return res;
    }

    void dfs(TreeNode* node, int curSum){
        if(node==nullptr) return;
        if(m.count(curSum-sum))
            res += m[curSum-sum];
        m[curSum]++;

        if(node->left)
            dfs(node->left, curSum+ node->left->val);
        if(node->right)
            dfs(node->right, curSum+ node->right->val);
        m[curSum]--;
    }
};