437. Path Sum III

找到一颗树中所有和为sum的路径

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

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

主要逻辑：

每个点都调用一个函数findPath，来寻找以当前节点为root的路径中和为sum的路径数量

int res = 0;
if (root.val == num) res++;
res += findPath(root.left, num - root.val) + findPath(root.right, num - root.val);
return res;

为了满足这个逻辑，需要base conditionif(root == null) return 0;判空，所以整个函数写成这样：

public int findPath(TreeNode root, int num) {
    if (root == null) return 0;
    int res = 0;
    if (root.val == num) {
        res++;
    }
    res += findPath(root.left, num - root.val) + findPath(root.right, num - root.val);
    return res;
}

pathSum主函数用来找到root，以及root.left和root.right的中满足条件路径的数量。

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    int res = findPath(root, sum);
    res += pathSum(root.left, sum) + pathSum(root.right, sum);
    return res;
}

完整代码：

public int pathSum(TreeNode root, int sum) {
    if (root == null) return 0;
    int res = findPath(root, sum);
    res += pathSum(root.left, sum) + pathSum(root.right, sum);
    return res;
}

public int findPath(TreeNode root, int num) {
    if (root == null) return 0;
    int res = 0;
    if (root.val == num) {
        res++;
    }
    res += findPath(root.left, num - root.val) + findPath(root.right, num - root.val);
    return res;
}