112. 路径总和
-
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
-
叶子节点 是指没有子节点的节点。
1. 深度优先搜索(DFS)
- 首先判断根节点是否为空。如果为空，则返回 False
- 然后检查当前节点是否是叶子节点（即同时没有左右子树）。如果是叶子节点，判断当前节点的值是否等于目标和 targetSum
- 如果不是叶子节点，则递归检查左右子树。每递归一次，targetSum 减去当前节点的值。当递归到叶子结点时，若叶子结点的值等于递减的targetSum，说明该路径总和为targetSum，返回True（该判断执行在第2步）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if not root:return False# 如果当前节点是叶子节点(即该节点的左右子树同时为空时)，并且目标和与当前节点的值相等，返回 Trueif not root.left and not root.right:return targetSum == root.val# 否则，递归检查左右子树targetSum -= root.valreturn self.hasPathSum(root.left, targetSum) or self.hasPathSum(root.right, targetSum)
- return A or B：返回 A 或 B 中第一个值为 True 的那个，如果都为 False，则返回 B
深度优先搜索的时间复杂度和空间复杂度
- 时间复杂度：O(n), n为节点数
- 空间复杂度：O(h), h为树的高度
2. 广度优先搜索(BFS)
- 从根节点开始，初始化队列，将根节点和当前路径的和（即 targetSum - root.val）加入队列
- 遍历队列中的每一个元素，每次取出一个节点及其当前的路径和：
- 如果该节点是叶子节点，并且当前路径和等于目标和，则返回 True，表示找到了符合条件的路径
- 否则，将该节点的左右子节点以及更新后的路径和添加到队列中
- 如果遍历完所有节点仍然没有找到符合条件的路径，返回 False
from collections import deque
# deque 允许从队列的两端进行操作，不仅仅是从队尾。class Solution(object):def hasPathSum(self, root, targetSum):""":type root: Optional[TreeNode]:type targetSum: int:rtype: bool"""if not root:return False# 使用队列进行 BFSqueue = deque([(root, targetSum - root.val)]) # deque将队列转变为双端队列, 即可以在队列双端进行添加和删除操作# 队列queue 中的每个元素是一个元组，元组中存储了(节点, 当前路径和)# 遍历队列中的每个元素while queue:node, current_sum = queue.popleft() # 从队列中取出当前节点和路径和# node是当前节点# current_sum 是从根节点到当前节点的路径和（即从根节点到该节点的路径的和减去目标和的部分）# queue.popleft(): 从队列的左端弹出（删除并返回）一个元素# 如果是叶子节点且路径和等于目标和，返回 Trueif not node.left and not node.right and current_sum == 0:return True# 依序将左子节点和右子节点添加到队列中if node.left:queue.append((node.left, current_sum - node.left.val))if node.right:queue.append((node.right, current_sum - node.right.val))# 如果遍历完所有节点没有找到符合条件的路径，返回 Falsereturn False
-
执行流程
-
假设有以下树
5/ \4 8 / / \ 11 13 4 / \ / \ 7 2 5 1-
初始队列：[(5, 17)] （目标和是 22，根节点值是 5，因此路径和为 22 - 5 = 17）
-
第 1 次循环：取出 5，当前路径和 17。5 不是叶子节点，因此将其左右子节点 4 和 8 加入队列
队列更新：[(4, 13), (8, 9)]
-
第 2 次循环：取出 4，当前路径和 13。4 不是叶子节点，将其左子节点 11 加入队列
队列更新：[(8, 9), (11, 2)]
-
第 3 次循环：取出 8，当前路径和 9。8 不是叶子节点，将其左右子节点 13 和 4 加入队列
队列更新：[(11, 2), (13, -4), (4, 5)]
-
第 4 次循环：取出 11，当前路径和 2。11 不是叶子节点，将其左右子节点 7 和 2 加入队列
队列更新：[(13, -4), (4, 5), (7, -5), (2, 0)]
-
第 5 次循环：取出 13，当前路径和 -4。13 是叶子节点，路径和不为 0，不符合条件
-
第 6 次循环：取出 4，当前路径和 5。4 不是叶子节点，将其左右子节点 5 和 1 加入队列
队列更新：[(7, -5), (2, 0), (5, 0), (1, 4)]
-
第 7 次循环：取出 7，当前路径和 -5。7 是叶子节点，路径和不为 0，不符合条件
-
第 8 次循环：取出 2，当前路径和 0。2 是叶子节点，路径和为 0，返回 True，找到符合条件的路径
-
-
deque()的用法
-
添加元素：
- append(x)：将元素 x 添加到队列的 右端（尾部）。
- appendleft(x)：将元素 x 添加到队列的 左端（头部）。
-
删除元素：
- pop()：从队列的 右端删除并返回元素。
- popleft()：从队列的 左端删除并返回元素。
-
查看队列的两端元素：
- d[0]：获取队列的左端元素。
- d[-1]：获取队列的右端元素。
-
其他常用方法：
- extend(iterable)：将可迭代对象 iterable 中的元素添加到队列的 右端。
- extendleft(iterable)：将可迭代对象 iterable 中的元素添加到队列的 左端。注意，它会将元素逆序添加。
- rotate(n)：将队列旋转 n 次。正值表示将元素移到右端，负值表示将元素移到左端。
-
广度优先搜索的时间复杂度和空间复杂度
- 时间复杂度：O(n)，其中 n 是节点数量
- 空间复杂度：O(n)，在树的 BFS 中，队列的最大大小是树的宽度，即最宽的一层节点数。最宽的一层可能有 n/2 个节点，因此空间复杂度为 O(n)