6-14 二叉树的非递归遍历PTA

### 关于二叉树非递归遍历的题目与解法

#### 层序遍历作为非递归遍历的一种形式

层序遍历是一种基于队列的数据结构来实现的方法，它按照层次顺序访问节点，即从根节点开始逐层向下扩展搜索[^2]。此方法非常适合用于解决特定类型的二叉树问题。

对于PTA平台上的练习题而言，存在一道经典的例子：判断给定的一棵二叉树是否为完全二叉搜索树以及求解两个节点之间的最近公共祖先等问题都涉及到对二叉树进行有效的遍历操作。这些题目不仅考察了学生对于基本概念的理解程度，同时也测试了解决实际编码挑战的能力。

#### 实现非递归遍历的关键技术要点

当采用非递归方式完成二叉树遍历时，通常会借助栈或队列这样的辅助数据结构来进行迭代处理：

- **前序遍历** 和 **中序遍历**: 可以通过显式地维护一个栈来模拟函数调用的过程；

- **后序遍历**: 则相对复杂一些，可能需要用到额外的空间记录已经访问过的子树；

- **层序遍历**: 使用队列保存待访问的节点列表，并依次取出当前节点并将其左右孩子加入到队列末端直至所有节点都被访问完毕。

下面给出一段Python代码片段展示如何利用队列执行简单的层序遍历:

from collections import deque

def level_order_traversal(root):
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        
        if not node:
            continue
            
        result.append(node.val)

        if node.left is not None:
            queue.append(node.left)
            
        if node.right is not None:
            queue.append(node.right)
                
    return result

这段代码实现了最基本的层序遍历逻辑，适用于大多数情况下验证理解或是初步学习阶段使用。