437. 路径总和 III(递归)-蒲公英云

437. 路径总和 III(递归)

437. 路径总和 III

题目
解题思路
代码

题目

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

在这里插入图片描述

解题思路

这题采用双递归的方式，但是依旧是按照递归的模板来（1.找到最简单的子问题求解，2.其他问题不考虑内在细节，只考虑整体逻辑）。

题目要求路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。这就要求我们只需要去求三部分即可：

以当前节点作为头结点的路径数量
以当前节点的左孩子作为头结点的路径数量
以当前节点的右孩子作为头结点啊路径数量

将这三部分之和作为最后结果即可。

但是注意我们要新写一个辅助方法，用来求上面三种情况的路径，并且在这个辅助函数里面还要递归调用。

即：假如现在传了一个root给辅助函数，因为“不需要在叶子节点结束”，所以每隔一个节点都要判断一次这一个节点的值满不满足要求，也就是sum-root.val是否为0.如果是结果路径+1，然后 “不管上一步的路径是否加1”我们都要去找root的左子树，右子树，即“找到一个节点要做的事，剩下的交给递归框架”

代码

class Solution {
     public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        int result = countPath(root,sum);
        int a = pathSum(root.left,sum);
        int b = pathSum(root.right,sum);
        return result+a+b;
    }
    public int countPath(TreeNode root,int sum){
        if(root == null){
            return 0;
        }
        sum = sum - root.val;//用sum减去root.val看是不是0；
        int result = sum == 0 ? 1:0;//如果是0，证明满足条件，路径为1
        int leftCount=countPath(root.left,sum);
        int rightCount=countPath(root.right,sum);
        return result + leftCount + rightCount;
    }
}