晋中市网站建设_网站建设公司_云服务器_seo优化

中序遍历（基于栈的非递归实现）和层序遍历（基于队列的实现）是二叉树遍历中的两种重要方法，分别体现了深度优先与广度优先的访问策略。

1. 中序遍历（非递归，基于栈）

definorder_traversal(root):stack=[]result=[]current=rootwhilecurrentorstack:# 一直向左走到底，将路径上节点入栈whilecurrent:stack.append(current)current=current.left# 当前为空，弹出栈顶并访问current=stack.pop()result.append(current.val)# 访问节点current=current.right# 转向右子树returnresult

该方式模拟了递归调用的过程，通过显式使用栈来保存回溯路径，确保在访问完左子树后能正确回到根节点再进入右子树。

2. 层序遍历（基于队列）

fromcollectionsimportdequedeflevel_order_traversal(root):ifnotroot:return[]queue=deque([root])result=[]whilequeue:node=queue.popleft()result.append(node.val)ifnode.left:queue.append(node.left)ifnode.right:queue.append(node.right)returnresult

利用先进先出的队列特性，保证每一层的节点按从左到右顺序被处理，适合用于求解树的层次结构相关问题，如层平均值、最大宽度等。

补充说明中强调：不同遍历方式生成的线性序列反映了不同的逻辑顺序。例如：

• 中序遍历对二叉搜索树可得到升序序列；
• 层序遍历则揭示了树的层级分布。

这些序列中所谓的“前驱”与“后继”关系依赖于具体的遍历规则，并无全局统一性。
前序遍历和后序遍历的非递归实现同样基于栈结构，但访问节点的顺序不同，因此入栈策略也有所区别。

1.前序遍历（根 → 左 → 右）非递归实现

核心思想：使用栈模拟递归过程。每次弹出一个节点并访问，然后先将其右子节点入栈，再将左子节点入栈（确保左子树优先被处理）。

defpreorder_traversal(root):ifnotroot:return[]stack=[root]result=[]whilestack:node=stack.pop()result.append(node.val)# 先压右再压左，保证左子树先出栈ifnode.right:stack.append(node.right)ifnode.left:stack.append(node.left)returnresult

2.后序遍历（左 → 右 → 根）非递归实现

后序遍历较复杂，因为根节点必须在左右子树都访问完之后才能输出。常用方法是“双栈法”或“标记法”。这里介绍简洁高效的双栈法：
思路：

• 第一个栈用于遍历，顺序为：根 → 左 → 右（类似前序）；
• 将访问的节点按此顺序压入第二个栈；
• 最终从第二个栈弹出时，顺序变为：根 ← 右 ← 左，即后序的逆序。

defpostorder_traversal(root):ifnotroot:return[]stack1=[root]# 主栈，用于遍历stack2=[]# 辅助栈，记录逆序结果whilestack1:node=stack1.pop()stack2.append(node)# 先压左再压右，保证右子树先处理ifnode.left:stack1.append(node.left)ifnode.right:stack1.append(node.right)# 弹出辅助栈得到后序序列result=[]whilestack2:result.append(stack2.pop().val)returnresult

💡 提示：也可以用单栈+指针标记已访问子树的方式实现，但双栈更直观易懂。

总结对比