zhangdi

112.路径总和 ​

题目 ​

LeetCode 简单

INFO

给你二叉树的根节点 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)

ts
function hasPathSum(root: TreeNode | null, targetSum: number): boolean {
  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 Tree([5, 4, 8, 11, null, 13, 4, 7, 2, null, null, null, 1])
console.log('🌰', hasPathSum(tree.root, 22))
console.log('🌰', hasPathSum(tree.root, 26))
console.log('🌰', hasPathSum(tree.root, 80))