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)

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function pathSum(root, target) {
  let res = []
  if (root) {
    let path = []
    const dfs = (root, target) => {
      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 TreeNode(5)
tree.left = new TreeNode(4, new TreeNode(11, new TreeNode(7), new TreeNode(2)))
tree.right = new TreeNode(
  8,
  new TreeNode(13),
  new TreeNode(4, new TreeNode(5), new TreeNode(1)),
)

console.log('🌰', JSON.stringify(pathSum(tree, 22)))
console.log('-----')
console.log('🌰', JSON.stringify(pathSum(tree, 9)))

执行结果

node 5 target 17 path [5]
node 4 target 13 path [5,4]
node 11 target 2 path [5,4,11]
node 7 target -5 path [5,4,11,7]
node 2 target 0 path [5,4,11,2]
node 8 target 9 path [5,8]
node 13 target -4 path [5,8,13]
node 4 target 5 path [5,8,4]
node 5 target 0 path [5,8,4,5]
node 1 target 4 path [5,8,4,1]
🌰 [[5,4,11,2],[5,8,4,5]]
-----
node 5 target 4 path [5]
node 4 target 0 path [5,4]
node 11 target -11 path [5,4,11]
node 7 target -18 path [5,4,11,7]
node 2 target -13 path [5,4,11,2]
node 8 target -4 path [5,8]
node 13 target -17 path [5,8,13]
node 4 target -8 path [5,8,4]
node 5 target -13 path [5,8,4,5]
node 1 target -9 path [5,8,4,1]
🌰 []

本页目录

题目

题解

方法：递归