二叉树层次遍历

"分行从上往下打印二叉树是一种常见的二叉树遍历问题，通常出现在算法面试和编程竞赛中。这个题目要求我们按照层级顺序，自上而下逐行打印二叉树的节点值。给定的二叉树结构是一个典型的二叉链表表示，其中每个节点包含一个整数值、一个左子节点指针和一个右子节点指针。参考答案提供了一个C++实现的解决方案，使用队列进行广度优先搜索（BFS）来完成任务。" 在二叉树的遍历中，有三种主要方法：前序遍历（根-左-右），中序遍历（左-根-右）和后序遍历（左-右-根）。本题涉及的是层次遍历，也称为水平遍历，是前序遍历的一种变体，它按照二叉树的层级逐层进行。 参考答案中的C++代码首先定义了一个`TreeNode`结构体，用于表示二叉树的节点，包含节点值`val`、左子节点`left`和右子节点`right`。接着，定义了一个名为`Solution`的类，其中有一个成员函数`printFromTopToBottom`，用于实现层次遍历。 `printFromTopToBottom`函数接受一个`TreeNode`类型的指针作为参数，即二叉树的根节点。为了遍历二叉树，它使用了广度优先搜索策略，这是通过一个队列`q`来实现的。队列中首先加入根节点，然后加入一个`NULL`节点作为当前层级结束的标志。同时，定义了一个`vector<int>`类型的`cur`，用于存储当前层的节点值。 在循环中，当队列不为空时，取出队列头部的节点。如果该节点非空，将其值添加到`cur`中，并将它的左右子节点（如果存在）推入队列。如果取出的节点是`NULL`，说明当前层已处理完毕，将`cur`添加到结果集`res`中，并清空`cur`以准备存储下一层的节点值。循环继续，直到队列为空。 最后，返回结果集`res`，它包含了二叉树每一层的节点值，以二维数组的形式表示。在样例中，输入的二叉树结构转换为文字描述是这样的： ``` 8 / \ 12 2 / 6 / 4 ``` 对应的输出是`[[8], [12, 2], [6], [4]]`，表示从上到下、从左到右的层级顺序。 总结来说，这个题目考察的是对二叉树层次遍历的理解和实现，以及如何利用广度优先搜索策略解决这类问题。在实际应用中，层次遍历常用于寻找最近公共祖先、求解二叉树的最大宽度等问题。