引言以BFS一般以队列辅助实现而DFS既能用栈实现又能用递归系统栈实现。BFS 不是绝对不能递归实现而是天然不适合递归DFS才是递归的天然选择。概念解析- DFS深度优先一条路走到黑遇到岔路先往下钻。调用栈天然就是DFS的栈递归的函数调用栈 DFS栈完美匹配。-递归DFS遇到节点 → 递归访问子节点系统栈保存现场- BFS广度优先按层遍历。先访问第0层再全部第1层再全部第2层要用队列Queue。队列与栈的对立性栈和队列的数据结构本身是相反的。队列特点先进先出 FIFO递归依靠的是调用栈后进先出 LIFO。递归BFS伪代码def bfs_recursive(q):if not q: #队列为空终止returnnode q.pop(0) #出队visit(node)#把邻居加入队列for neighbor in node.neighbors:if not visited[neighbor]:visited[neighbor] Trueq.append(neighbor)bfs_recursive(q) #递归调用继续处理当前队列递归BFS缺点1.普通循环BFS简单高效递归版本不仅没简化逻辑还引入递归开销函数调用、压栈出栈速度更慢。1、利用函数调用栈做BFS必须自己额外传队列参数。2、递归实现的本质就是把while循环改成递归没有利用递归栈的优势。真正保存BFS层次信息的是你手动写的队列不是系统调用栈。2. 容易栈溢出。递归每处理一层就增加一层函数调用。如果树/图层数很深递归次数太多直接触发栈溢出 stack overflow 【栈溢出即超出预定义静态空间那么DFS就不会栈溢出了吗】。普通循环BFS用的是堆上的队列几乎不会出现这个问题。【为什么呢】3. 可读性差违背BFS思想。BFS的核心就是“一层一层处理”用while队列直观。强行递归写法别扭别人读代码很难理解。BFS队列实现_二叉树层序遍历from collections import dequedef levelOrder(root):if not root:return []q deque([root])res[]while q:level[]for _ in range(len(q)):nq.popleft()level.append(n.val)if n.left: q.append(n.left)if n.right: q.append(n.right)res.append(level)return res