C++刷leetcode（437. 路径总和 III）【递归】

糖逗

题目描述：

1. 给定一个二叉树，它的每个结点都存放着一个整数值。
   
2. 
   
3. 找出路径和等于给定数值的路径总数。
   
4. 
   
5. 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
   
6. 
   
7. 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
   
8. 
   
9. 示例：
   
10. 
    
11. root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
12. 
    
13.       10
    
14.      /  \
    
15.     5   -3
    
16.    / \    \
    
17.   3   2   11
    
18. / \   \
    
19. 3  -2   1
    
20. 
    
21. 返回 3。和等于 8 的路径有:
    
22. 
    
23. 1.  5 -> 3
    
24. 2.  5 -> 2 -> 1
    
25. 3.  -3 -> 11
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/path-sum-iii
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     //soluiton实现的是以root为sum初始元素的和为sum的个数
   
4.     int solution(TreeNode*root, int sum){
   
5.         if(root == NULL) return 0;
   
6.         sum -= root -> val;
   
7.         return (sum == 0 ? 1 : 0) + solution(root -> left, sum) + solution(root -> right, sum);
   
8.     }
   
9.     //pathsSum实现的是以root为根的树和为sum的个数
   
10.     int pathSum(TreeNode* root, int sum) {
    
11.         if(root == NULL) return 0;
    
12.         return solution(root, sum) + pathSum(root -> left, sum) + pathSum(root -> right, sum);
    
13.     }
    
14. };

复制代码

参考链接：
1.https://leetcode-cn.com/problems ... -yu-fei-di-gui-fan/

糖逗

需要再看一遍，有点儿绕。