Repository navigation
112. 路径总和 #77
Description
递归
- 处理边界，节点不存在时返回 false
- 左右子树都不存在时代表是叶子结点，判断是否符合条件
- 递归左右子树时进行转换，看能否找到
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 是树的高度
Activity