深度&广度优先搜索
本文将以LeetCode的例题为例子，用Python语言实现深度优先、广度优先搜索。
DFS/深度优先
Section titled “DFS/深度优先”例题：Increasing Order Search Tree
题意：前序深度优先遍历即可。
因为要求一个特定的输出格式，所以先简单实现这部分的逻辑
# 将当前节点保存到结果树的最右端（构建一条右斜链表） def saveResult(self, node: TreeNode) -> None: # 递归基：空节点直接返回，不作处理 if node == None: return # print(node.val)
# 第一个有效节点：作为结果树的根节点 if self.result == None: self.result = TreeNode(node.val, None, None) self.resultTop = self.result # resultTop 始终指向结果树的最右节点 # 后续节点：挂到结果树的最右端 else: self.resultTop.right = TreeNode(node.val, None, None) self.resultTop = self.resultTop.right # 更新最右节点指针递归形式的深度优先很好写：
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def increasingBST(self, root: TreeNode) -> TreeNode: self.result = None # 初始化结果树为空 self.dfs(root) # 中序遍历：保证输出结果是升序的 return self.result
def dfs(self, root: TreeNode) -> None: # 递归终止条件：空节点直接返回 if root == None: return # 中序遍历：左 → 根 → 右 self.dfs(root.left) # 先处理左子树 self.saveResult(root) # 再处理当前节点（将值添加到结果树） self.dfs(root.right) # 最后处理右子树简单来说，注意None的判断，以及是前序中序还是后序就行。
这里也提供一个用栈替代递归实现的版本：
# 用栈模拟中序遍历的迭代版本（递归的显式化） def dfs(self, root: TreeNode) -> None: # 空树直接返回 if root == None: return stack = [root] # 初始化栈，放入根节点
while (len(stack) != 0): # 栈非空时不断处理
top = stack.pop() # 弹出栈顶元素（后进先出） # print(len(stack))
# 叶子节点：左右都为空，可以直接处理 if top.left == None and top.right == None: self.saveResult(top) # 非叶子节点：需要先处理左右子树，再处理自身 else: left = top.left right = top.right # 关键：将当前节点的左右指针断开，避免后续重复遍历 top.left = None top.right = None
# 压栈顺序（因为是后进先出，所以反着放）：右 → 自身 → 左 # 这样处理顺序就是 左 → 自身 → 右，即中序遍历 if right != None: stack.append(right) stack.append(top) # 自身变为叶子节点后重新压栈 if left != None: stack.append(left)简单来说，用栈的是否为空来一直遍历，取出栈的首个元素，并按照顺序反向压进栈即可。
有一个需要注意的事情是这里将处理的栈定元素手动变成了叶子节点重新压栈，因为不是中序遍历，后续再处理到这个元素如果没有取出左右相连节点，会再次将左右相连节点压栈从而死循环。
BFS/广度优先
Section titled “BFS/广度优先”题意：对根节点右边的子树进行反向的遍历与左边比较即可。
这里其实不一定严格要广度优先，不过广度优先是最普遍的遍历树的打印方式。
# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def isSymmetric(self, root: TreeNode) -> bool: # 空树视为对称 if root == None: return True left = [] # 存储左子树的遍历序列 right = [] # 存储右子树的遍历序列 # 左子树按正序（左→右）遍历，右子树按镜像序（右→左）遍历 self.bfsLeft(root.left, left) self.bfsRight(root.right, right)
# print(left) # print(right) # 两个序列相等则说明树是对称的 return left == right
def bfsLeft(self, root: TreeNode, result: list): queen = [root] # 用列表模拟队列，存储待访问节点
while len(queen) != 0: # 队列非空则继续 top = queen.pop(0) # 队首出队（pop(0)模拟FIFO）
if top != None: result.append(top.val) # 记录节点值 queen.append(top.left) # 左子节点入队 queen.append(top.right) # 右子节点入队 else: # 空节点也要记录，用于比较结构对称性 result.append(None)
return result
def bfsRight(self, root: TreeNode, result: list): queen = [root] # 用列表模拟队列
while len(queen) != 0: top = queen.pop(0) # 队首出队
if top != None: result.append(top.val) # 记录节点值 # 关键：与bfsLeft相反，先右后左，实现镜像遍历 queen.append(top.right) queen.append(top.left) else: # 空节点同样记录，保证结构的一一对应 result.append(None)
return result用队列实现，其实还算简单，不过这里因为空值也要比较所以空值的处理方式不太一样。
当然也可以用递归形式的DFS实现：
# 递归形式的 DFS 遍历（实际是前序深度优先，但输出格式模仿 BFS 层序） def bfsLeft(self, top: TreeNode, result: list):
if top != None: result.append(top.val) # 先记录当前节点的值 self.bfsLeft(top.left, result) # 递归处理左子树 self.bfsLeft(top.right, result) # 递归处理右子树 else: # 空节点也要标记，保留结构信息用于对称比较 result.append(None)
return result
# 镜像版本：处理右子树时左右顺序颠倒，与 bfsLeft 形成对称 def bfsRight(self, top: TreeNode, result: list):
if top != None: result.append(top.val) # 先记录当前节点的值 self.bfsRight(top.right, result) # 先递归右子树（镜像操作） self.bfsRight(top.left, result) # 再递归左子树（镜像操作） else: # 空节点同理，保证序列长度和结构一致 result.append(None)
return result如果硬要用递归本质的DFS来模仿BFS的打印的话，可以考虑引入额外的标记字段 不过就有点得不尝试，毕竟DFS很容易爆栈，而BFS则可以比较方便的控制队列大小。