* Definition for a binary tree node.
* function TreeNode(val) {
* this.left = this.right = null;
// the number of the paths starting from self
function helper(root, sum) {
if (root === null) return 0;
const l = helper(root.left, sum - root.val);
const r = helper(root.right, sum - root.val);
return l + r + (root.val === sum ? 1 : 0);
var pathSum = function (root, sum) {
// 空间复杂度O(n) 时间复杂度介于O(nlogn) 和 O(n^2)
if (root === null) return 0;
// the number of the paths starting from self
const self = helper(root, sum);
// we don't know the answer, so we just pass it down
const l = pathSum(root.left, sum);
// we don't know the answer, so we just pass it down
const r = pathSum(root.right, sum);