437. 路径总和 III--🀄️

437. 路径总和 III

难度中等 763

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

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

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

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

示例：

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10

/  \

5   -3

/ *\*    *\*

3   2   11

/ \   ****

3  -2   1

返回 3。和等于 8 的路径有:

1. 5 -> 3

2. 5 -> 2 -> 1

3. -3 -> 11.

 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;
        int result = sum == 0 ? 1:0;
        return result + countPath(root.left,sum) + countPath(root.right,sum);
    }

作者：Geralt_U
链接：https://leetcode-cn.com/problems/path-sum-iii/solution/437lu-jing-zong-he-iii-di-gui-fang-shi-by-ming-zhi/

解析

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

以当前节点作为头结点的路径数量

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

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

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

最后的问题是：我们应该如何去求以当前节点作为头结点的路径的数量？这里依旧是按照树的遍历方式模板，每到一个节点让 sum-root.val，并判断 sum 是否为 0，如果为零的话，则找到满足条件的一条路径。