题解 | #二叉树中和为某一值的路径(三)#

二叉树中和为某一值的路径(三)：最直观的想法是，首先编写一个以某一节点为路径起始节点的求给定值的函数，其相对于(一)的区别是终止条件部分不要求必须是叶子节点且对应的执行操作是将满足要求的路径数量加一，而且这个终止部分不能直接返回，因为其路径中可能存在负值，从而出现正负抵消的情况。然后由于起始节点不一定是根节点，故对二叉树执行前序遍历，在遍历到当前节点时，再调用以该节点为路径起始节点的函数。

int pathnum=0; // 记录满足要求的路径数量
void dfs(TreeNode* root, int sum)
{
   if(!root)
     return;
   // 结束不一定是叶子结 但结束也不一定直接直接返回 因为可能有负值
   // {1,0,1,1,2,0,-1,0,1,-1,0,-1,0,1,0}
   if(root && root->val==sum)
      pathnum++;
   dfs(root->left,sum-root->val);
   dfs(root->right,sum-root->val);
}
// 树的前序遍历
int FindPath(TreeNode* root, int sum) 
{
    if(!root)
       return 0;
    // 根节点 以当前root为根结点的满足要求的路径数
    dfs(root,sum);
    // 左节点 左子树满足要求的路径数
    FindPath(root->left, sum);
    // 右节点 右子树满足要求的路径数
    FindPath(root->right, sum);
    return pathnum;
}