112. 路径总和 🟩

题目

LeetCode 简单

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。
判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum。如果存在，返回 true；否则，返回 false。

示例：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如图所示。

题解

方法：递归

深度优先 DFS 递归

时间复杂度：O(n)
空间复杂度：O(h)

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

function hasPathSum(root, targetSum) {
  if (!root) return false

  console.log('node', root.val, 'targetSum', targetSum)

  if (!root.left && !root.right) return root.val === targetSum
  targetSum = targetSum - +root.val
  return hasPathSum(root.left, targetSum) || hasPathSum(root.right, targetSum)
}

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, null, new TreeNode(1)),
)

console.log('🌰', hasPathSum(tree, 22)) 
console.log('-----')
console.log('🌰', hasPathSum(tree, 26)) 
console.log('-----')
console.log('🌰', hasPathSum(tree, 9))

执行结果

node 5 targetSum 22
node 4 targetSum 17
node 11 targetSum 13
node 7 targetSum 2
node 2 targetSum 2
🌰 true
-----
node 5 targetSum 26
node 4 targetSum 21
node 11 targetSum 17
node 7 targetSum 6
node 2 targetSum 6
node 8 targetSum 21
node 13 targetSum 13
🌰 true
-----
node 5 targetSum 9
node 4 targetSum 4
node 11 targetSum 0
node 7 targetSum -11
node 2 targetSum -11
node 8 targetSum 4
node 13 targetSum -4
node 4 targetSum -4
node 1 targetSum -8
🌰 false

本页目录

题目

题解

方法：递归