leetcode 437. Path Sum III 深度优先遍历DFS+两个递归函数

清疚 2022-06-04 08:20 153阅读 0赞

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

题意很简单，就是DFS深度优先遍历求解

建议和[leetcode 112. Path Sum DFS深度优先遍历][leetcode 112. Path Sum DFS] 和[leetcode 113. Path Sum II DFS深度优先遍历][leetcode 113. Path Sum II DFS] 一起学习

还有[leetcode 124. Binary Tree Maximum Path Sum 最大路径和 + DFS深度优先搜索][leetcode 124. Binary Tree Maximum Path Sum _ _ DFS] 和 [leetcode 687. Longest Univalue Path 深度优先遍历DFS][leetcode 687. Longest Univalue Path _DFS] 一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    /*
    struct TreeNode
    {
         int val;
         TreeNode *left;
         TreeNode *right;
         TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        int pathSum(TreeNode* root, int sum) 
        {
            if (root == NULL)
                return 0;
            else
                return dfs(root, 0, sum) + pathSum(root->left,sum) + pathSum(root->right, sum);
        }
    
        int dfs(TreeNode* root, int cur, int sum)
        {
            if (root == NULL)
                return 0;
            else
            {
                cur += root->val;
                if (cur == sum)
                    return 1 + dfs(root->left, cur, sum) + dfs(root->right, cur, sum);
                else
                    return dfs(root->left, cur, sum) + dfs(root->right, cur, sum);
            }
        }
    };

[leetcode 112. Path Sum DFS]: http://blog.csdn.net/jackzhang_123/article/details/77962275
[leetcode 113. Path Sum II DFS]: http://blog.csdn.net/jackzhang_123/article/details/77978987
[leetcode 124. Binary Tree Maximum Path Sum _ _ DFS]: http://blog.csdn.net/JackZhang_123/article/details/77989142
[leetcode 687. Longest Univalue Path _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78880772