0 题目描述
leetcode原题链接:112. 路径总和
1 递归解法
假定从根节点到当前节点的值之和为 val,我们可以将这个大问题转化为一个小问题:是否存在从当前节点的子节点到叶子的路径,满足其路径和为 sum - val。
不难发现这满足递归的性质,若当前节点就是叶子节点,那么我们直接判断 sum 是否等于 val 即可(因为路径和已经确定,就是当前节点的值,我们只需要判断该路径和是否满足条件)。若当前节点不是叶子节点,我们只需要递归地询问它的子节点是否能满足条件即可。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
if not root.left and not root.right:
return sum == root.val
return self.hasPathSum(root.left, sum-root.val) or self.hasPathSum(root.right, sum-root.val)
复杂度分析
- 时间复杂度:
O
(
N
)
,
O(N),
O(N), 其中
N
N
N 是树的节点数。对每个节点访问一次。
- 空间复杂度:
O
(
H
)
O (H)
O(H), 其中
H
H
H 是树的高度。空间复杂度主要取决于递归时栈空间的开销, 最坏情 况下,树呈现链状,空间复杂度为
O
(
N
)
O(N)
O(N) 。平均情况下树的高度与节点数的对数正相关,空间复杂度为
O
(
log
N
)
。
O(\log N)_{\text {。 }}
O(logN)。
参考资料
路径总和 - I