Java实现二叉树层次遍历

"Day06_剑指Offer.md" 在给定的代码中，我们有两个Java类，它们分别实现了从上到下层次遍历二叉树（Level Order Traversal）的方法。层次遍历是一种常见的二叉树遍历策略，它按照从上到下、从左到右的顺序逐层打印二叉树的节点。 第一个类`LevelOrder`包含一个内部类`TreeNode`，用于表示二叉树的节点结构，以及一个`levelOrder`方法来执行层次遍历。以下是关键知识点的详细说明： 1. **二叉树节点定义**： - `TreeNode`类具有一个整型变量`val`表示节点的值，以及两个`TreeNode`类型的引用`left`和`right`，分别表示左子节点和右子节点。 - 构造函数`TreeNode(int x)`用于创建一个新的节点，并将给定的值`x`赋给`val`。 2. **层次遍历实现**： - `levelOrder`方法接受一个`TreeNode`类型的根节点作为输入。 - 如果根节点为空，返回一个空数组，表示没有节点需要遍历。 - 使用`LinkedList`实现的`Queue`作为辅助数据结构，用于存储待处理的节点。 - 初始化一个`ArrayList`来保存遍历结果。 - 将根节点入队，然后进入一个循环，只要队列不为空，就继续遍历。 - 出队一个节点，将其值添加到结果列表中。 - 如果当前节点有左子节点，将其入队。 - 如果当前节点有右子节点，也将其入队。 - 循环结束后，将结果列表转换成整型数组`res`并返回。 第二个类似乎不完整，但根据类名和注释，它可能是为了实现与第一个类类似的功能，即层次遍历。不过，这个类缺少了具体的实现代码。 层次遍历的算法通常使用广度优先搜索（BFS）策略，这里使用了队列作为主要的数据结构，体现了BFS的特点。在实际应用中，层次遍历可以用于解决很多问题，比如找出二叉树的宽度、找到最近公共祖先等。 这段代码提供了二叉树层次遍历的一个清晰实现，通过队列的入队和出队操作，确保了层次顺序的正确性。