二叉树层次遍历与对称性判断算法详解

在剑指offer的编程题目中，我们关注的是与二叉树相关的两个问题：一是将二叉树按层次顺序打印（层序遍历），二是判断一棵二叉树是否是对称的。 **第一部分：层序遍历二叉树** 题目要求我们从上到下按层次打印二叉树，即对每个节点执行广度优先搜索(BFS)算法。在C++代码中，定义了一个`Solution`类，其中`Print`函数是解决这个问题的关键。首先，创建一个空的结果向量`res`用于存储每一层的节点值。然后，初始化一个队列`q`，并将根节点`pRoot`入队。接下来，进入一个循环，直到队列不为空： 1. 创建一个临时向量`temp`来保存当前层的节点值。 2. 获取队列的大小`sz`，表示当前层的节点数量。 3. 遍历这一层的所有节点： - 取出队列中的第一个节点`cur`，将其值添加到`temp`中。 - 如果`cur`有左子节点，将其加入队列。 - 如果`cur`有右子节点，也将其加入队列。 4. 遍历完一层后，将`temp`添加到结果向量`res`中，并更新队列。 5. 当队列为空时，表示已处理完所有节点，返回结果`res`。 **第二部分：判断二叉树对称性** 第二个问题是判断一棵二叉树是否对称，即它的左右子树结构是否完全相同。这里采用递归方法，定义一个辅助函数`f`，它接受两个节点作为参数。如果两个节点都为空，则返回`true`；若其中一个为空而另一个不为空，则返回`false`，因为对称性要求左右子树结构相等。对于非空节点，比较它们的左子节点和右子节点，如果`f(root1->left, root2->right)`以及`f(root1->right, root2->left)`都返回`true`，则说明当前节点及其子树对称，返回`true`。否则，返回`false`。 总结这两个问题，剑指offer中的挑战主要集中在利用BFS算法进行层次遍历和通过递归实现对称性判断。理解并掌握这两种算法是解决这类二叉树问题的基础，熟练运用后能帮助提升数据结构和算法在实际编程中的应用能力。