二叉树层次遍历的两种方法解析

"二叉树层次遍历的C++实现" 在给定的代码中，主要涉及了二叉树层次遍历的实现方法，这是一种常见的数据结构问题，通常出现在编程面试和在线平台如LeetCode的练习中。二叉树层次遍历又称为二叉树的层次访问，它按照从上至下、从左至右的顺序逐层遍历树的节点。 二叉树层次遍历的两种方法如下： 1. **借助辅助队列的迭代方法**：这是最常见的方法，代码中也使用了这种方法。首先创建一个队列`queue<TreeNode*>`，将根节点放入队列。然后，使用两个变量`num_1`和`num_2`来跟踪当前层和下一层的节点数量。在每次循环中，处理当前层的所有节点，将它们的子节点加入队列，并更新下一层的节点数。同时，用一个向量`level_vector`存储当前层的节点值。当队列为空时，表示所有节点都被遍历，遍历结束。 ```cpp // 迭代法 vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> ret_val; vector<int> level_vector; queue<TreeNode*> qn; // ... 初始化和边界条件检查 ... while (!qn.empty()) { num_1 = num_2; num_2 = 0; level_vector.clear(); for (int i = 0; i < num_1; i++) { temp = qn.front(); qn.pop(); // ... 处理节点并添加子节点到队列 ... level_vector.push_back(temp->val); } ret_val.push_back(level_vector); } return ret_val; } ``` 2. **前序递归遍历**：虽然在代码中没有给出，但也可以通过前序递归遍历配合层次计算实现层次遍历。在前序遍历的过程中，记录当前层次的节点数，每进入新的一层就将当前层的节点值保存在一个向量中。然而，这种方法通常不如迭代法简洁和高效。 `TreeNode` 结构体定义了二叉树的节点，包括整数值`val`，以及左右子节点指针`left`和`right`。在代码中，`TreeNode`的构造函数用于方便地创建新节点。 这段代码展示了如何使用C++实现二叉树层次遍历，对于理解和解决类似问题非常有帮助。同时，它也体现了数据结构和算法在实际编程中的应用，尤其是在面试和在线编程挑战中。对于学习和提升C++编程技巧以及数据结构与算法知识的开发者来说，这是一个很好的实践案例。