给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

思路

  1. 递归，传递路径节点和剩余值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var pathSum = function (root, targetSum) {
  const result = []
  const searchPaths = function (root, targetSum, curVals) {
    if (!root) {
      return false
    }
    const remain = targetSum - root.val
    curVals = [...curVals, root.val]
    if (!root.left && !root.right) {
      if (remain === 0) {
        result.push(curVals)
      }
      return
    }
    return searchPaths(root.left, remain, curVals) || searchPaths(root.right, remain, curVals)
  }
  searchPaths(root, targetSum, [])
  return result
}