118 - 437 路径综合3

题目

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

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

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

二叉树不超过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

解答

双递归

https://leetcode-cn.com/problems/path-sum-iii/solution/leetcode-437-path-sum-iii-by-li-xin-lei/

问题拆分成，从根节点到任意节点和为sum，然后加上左右子树。

var paths = function(root, sum) {
  if (root === null) {
    return 0
  }
  let res = 0
  if (root.val === sum) {
    res++
  }
  res += paths(root.left, sum - root.val)
  res += paths(root.right, sum - root.val)
  return res
}
var pathSum = function(root, sum) {
  if (root === null) {
    return 0
  }
  return paths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
};

Runtime: 68 ms, faster than 91.48% of JavaScript online submissions for Path Sum III.

Memory Usage: 37 MB, less than 83.33% of JavaScript online submissions for Path Sum III.

func paths(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    res := 0
    if root.Val == sum {
        res++
    }
    res += paths(root.Left, sum-root.Val)
    res += paths(root.Right, sum-root.Val)
    return res
}
func pathSum(root *TreeNode, sum int) int {
    if root == nil {
        return 0
    }
    return paths(root, sum) + pathSum(root.Left, sum) + pathSum(root.Right, sum)
}

Runtime: 24 ms, faster than 10.53% of Go online submissions for Path Sum III.

Memory Usage: 4.4 MB, less than 20.00% of Go online submissions for Path Sum III.