zhangdizhangdi

113.路径总和 II

题目

LeetCode 中等

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

示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

题解

方法：深度优先

DFS 递归 O(n) O(h)

ts
function pathSum(root: TreeNode | null, target: number): number[][] {
  let res = []
  if (root) {
    let path = []
    const dfs = (root: TreeNode, target: number) => {
      if (!root) return
      path.push(root.val)
      target -= +root.val

      console.log('node', root.val, 'target', target, 'path', path)

      if (!root.left && !root.right && target === 0) {
        res.push([...path])
      }

      dfs(root.left, target)
      dfs(root.right, target)
      path.pop()
    }
    dfs(root, target)
  }
  return res
}

const tree = new Tree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1]),
  targetSum = 22
console.log('🌰', pathSum(tree.root, targetSum))