在蓝桥杯的备考冲刺阶段，非线性数据结构中的二叉树遍历算法是一个重要的考点。本文将深入总结递归、迭代和 Morris 遍历的实现差异，并附上层序遍历队列优化的代码模板，帮助考生更好地理解和掌握这一知识点。
一、二叉树遍历概述
二叉树的遍历是指按照某种顺序访问二叉树中的所有节点。常见的遍历方式有前序遍历、中序遍历、后序遍历和层序遍历。
二、递归遍历
递归遍历是最直观、最简单的遍历方式。它通过函数调用自身来遍历左右子树。
例如，中序递归遍历的代码如下：
def inorder_recursive(root):
if root:
inorder_recursive(root.left)
print(root.val)
inorder_recursive(root.right)
递归遍历的优点是代码简洁易懂，但缺点是当树的深度较大时，可能会导致栈溢出。
三、迭代遍历
为了避免递归的栈溢出问题，可以使用迭代的方式实现遍历。迭代遍历通常使用栈来模拟递归的过程。
中序迭代遍历的代码如下：
def inorder_iterative(root):
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
print(current.val)
current = current.right
迭代遍历的优点是避免了栈溢出，但代码相对复杂一些。
四、Morris 遍历
Morris 遍历是一种空间复杂度为 O(1) 的遍历方式，它通过利用树的空闲指针来实现遍历。
中序 Morris 遍历的代码如下：
def inorder_morris(root):
current = root
while current:
if not current.left:
print(current.val)
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
pre.right = current
current = current.left
else:
pre.right = None
print(current.val)
current = current.right
Morris 遍历的优点是空间复杂度低，但会修改树的结构。
五、层序遍历队列优化
层序遍历通常使用队列来实现。为了优化层序遍历的性能，可以使用双端队列（deque）来代替普通队列。
层序遍历的代码如下：
from collections import deque
def level_order(root):
if not root:
return []
queue = deque([root])
result = []
while queue:
level_size = len(queue)
level_nodes = []
for _ in range(level_size):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_nodes)
return result
六、总结
在备考过程中，考生需要深入理解递归、迭代和 Morris 遍历的实现原理和差异，并熟练掌握层序遍历的队列优化方法。通过大量的练习和总结，考生可以在蓝桥杯考试中灵活运用这些知识点，取得好成绩。
希望本文对您的备考有所帮助，祝您在蓝桥杯考试中取得优异的成绩！
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
