[leetcode]: 437. Path Sum III

柔光的暖阳◎ 2022-06-15 10:51 138阅读 0赞

# 1.题目 #

You are given a binary tree in which each node contains an integer value.  
Find the number of paths that sum to a given value.  
The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).  
The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.  
给一棵二叉树，求一共有多少条路径满足该路径上节点的和为指定值。  
Example:  
root = \[10,5,-3,3,2,null,11,3,-2,null,1\], sum = 8

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

Return 3. The paths that sum to 8 are:

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

# 2.分析 #

**方法1**  
DFS，对于每个节点：  
1）以当前节点为终点的路径和是否等于target  
2）以当前节点为起点开始新的路径  
**方法2**  
DFS+哈希表记录前缀和  
(key,value)–(prefix sum, num)  
前缀和：从根节点到途中某节点的路径和，例如

> 路径： 1,2,-1,-1,2  
> 前缀和： 1, 3, 2, 1, 3,

num–前缀和为prefix sum的路径条数  
–为什么计算前缀和？  
目标：以当前节点为终点的路径和满足target的路径有多少条

> 某节点到当前节点的路径和=根节点到当前节点的路径和-根节点到某节点的路径和

最后一项“根节点到某节点的路径和”就是前缀和。  
知道了有多少条路径的前缀和满足该等式就知道了有多少条路径以当前节点为终点且路径和为target.

# 3.代码 #

前缀和

class Solution {
    public:
        int getPathSum(TreeNode* root, unordered_map<int, int>& prefix, int curv, int sum) {
            if (root == NULL)
                return 0;
            curv += root->val;
            int count = (curv==sum) + prefix[curv - sum];//满足以当前节点为终点sum-prev=curv的前缀和有多少个
            prefix[curv] += 1;
            count += getPathSum(root->left, prefix, curv, sum) + getPathSum(root->right, prefix, curv, sum);//在加上左右子树
            prefix[curv] -= 1;//DFS是自底向上的，当遍历到高层节点时，需要去掉低层节点的prefix.
            return count;
        }
        int pathSum(TreeNode* root, int sum) {
            if (root == NULL)
                return 0;
            unordered_map<int, int> prefix;
            return getPathSum(root, prefix, 0, sum);
        }
    };

DFS

class Solution {
        
    public:
        int pathSum(TreeNode* root, int sum) {
            if (root == NULL)
                return 0;
            return getPathSum(root,0,sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
        }
        int getPathSum(TreeNode* root, int cur, int& sum) {
            if (root == NULL)
                return 0;
            cur+=root->val;
            return (cur == sum) + getPathSum(root->left, cur, sum) + getPathSum(root->right, cur, sum);
        }
    };