112. 路径总和

[Geekhyt]

原题链接

递归

1. 处理边界，节点不存在时返回 false
2. 左右子树都不存在时代表是叶子结点，判断是否符合条件
3. 递归左右子树时进行转换，看能否找到 targetSum - root.val 的路径

const hasPathSum = (root, targetSum) => {
  if (root === null) return false               
  if (root.left === null && root.right === null) {
    return targetSum - root.val === 0
  }
  return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
}

• 时间复杂度: O(n)
• 空间复杂度: O(H)，H 是树的高度