[数据结构与算法]LeetCode 437. 路径总和 III

437. 路径总和 III

?思路：

深度优先搜索，暴力搜索：

递归遍历每一个节点的所有可能路径，然后将这些路径书目加起来即为返回结果

首先定义rootSum(p,val)表示以节点p为起点向下且满足路径总和为val的路径数目。

对二叉树的每个节点求出 rootSum(p,target),然后对这些路径数目求和即为返回结果

问题转化为以p为根节点? 路径之和为targetSum的路径有多少条？

递归（深度优先搜索，暴力搜索）

? ? ? int? rootSum(p,targetSum):

? ? ? ? ? ? ? ? 以当前节点p为目标路径的起点递归向下进行搜索

假设当前的节点p为val

判断p->val是否等于targetSum

对左子树和右子树进行递归搜索：

对节点p的左孩子pl求出rootSum（pl,targetSum-val）

对节点p的右孩子节点pr求出rootSum(pr,targetSum-val)

节点p的rootsum（p，targetsum）=rootsum(pl,targetsum-val)+rootsum(pr,targetsum-val);

/**
 * 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 rootSum(TreeNode *root,int targetSum)
    {
        int sum=0;
        if(root==NULL)
        {
            return 0;
        }
       if(root->val==targetSum)
       sum++;
        sum+=rootSum(root->left,targetSum-root->val);
        sum+=rootSum(root->right,targetSum-root->val);
        return sum;
    }
    int pathSum(TreeNode* root, int targetSum) {
if(root==NULL)
return  0;
int n1=rootSum(root,targetSum);
int n2=pathSum(root->left,targetSum);
int n3=pathSum(root->right,targetSum);
    return n1+n2+n3;
}
    };