在 Java 中，层序遍历（也称为广度优先遍历）是一种遍历树或图的算法，它从树的根节点开始，逐层访问各个节点，确保同一层的节点都在下一层节点之前被访问。下面我将介绍三种不同的实现方式，每种方式都附带了相应的步骤流程和示例代码。
假设我们有以下的二叉树节点类：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
这是层序遍历的经典实现方式，利用队列的先进先出（FIFO）特性，从根节点开始，将每个节点的子节点按顺序加入队列，然后逐个访问队列中的节点。
步骤流程：
创建一个队列，将根节点入队。进入循环，直到队列为空： 3. 出队一个节点并访问。4. 将该节点的左子节点入队（如果存在）。 5. 将该节点的右子节点入队（如果存在）。
示例代码：
import java.util.LinkedList;
import java.util.Queue;
public class LevelOrderTraversal {
public static void levelOrder(TreeNode root) {
if (root == null)
return;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null)
queue.add(node.left);
if (node.right != null)
queue.add(node.right);
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Level Order Traversal:");
levelOrder(root);
}
}
Maven 依赖：
<!-- Add this to your pom.xml -->
<!-- No external dependencies needed for this implementation -->
Gradle 依赖：
// Add this to your build.gradle
// No external dependencies needed for this implementation
这种方式虽然不常见，但也可以通过递归实现层序遍历。它需要借助一个辅助方法，该方法遍历当前层的节点，并调用下一层的递归方法。
步骤流程：
示例代码：
import java.util.ArrayList;
import java.util.List;
public class LevelOrderTraversal {
public static void levelOrder(TreeNode root) {
int height = height(root);
for (int i = 1; i <= height; i++) {
levelOrderRecursive(root, i);
}
}
public static int height(TreeNode root) {
if (root == null)
return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
return Math.max(leftHeight, rightHeight) + 1;
}
public static void levelOrderRecursive(TreeNode root, int level) {
if (root == null)
return;
if (level == 1)
System.out.print(root.val + " ");
else if (level > 1) {
levelOrderRecursive(root.left, level - 1);
levelOrderRecursive(root.right, level - 1);
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Level Order Traversal:");
levelOrder(root);
}
}
Maven 依赖：
<!-- Add this to your pom.xml -->
<!-- No external dependencies needed for this implementation -->
Gradle 依赖：
// Add this to your build.gradle
// No external dependencies needed for this implementation
这是一种使用 Java 8 Stream API 的现代实现方式，它使用了 Lambda 表达式和 Stream 的功能来完成层序遍历。
步骤流程：
创建一个只包含根节点的列表。进入循环，直到列表为空： 3. 从列表中获取节点，访问节点值。将节点的非空子节点加入新的列表。
示例代码：
import java.util.ArrayList;
import java.util.List;
public class LevelOrderTraversal {
public static void levelOrder(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
TreeNode node = nodes.remove(0);
System.out.print(node.val + " ");
if (node.left != null)
nodes.add(node.left);
if (node.right != null)
nodes.add(node.right);
}
}
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
System.out.println("Level Order Traversal:");
levelOrder(root);
}
}
Maven 依赖：
<!-- Add this to your pom.xml -->
<!-- No external dependencies needed for this implementation -->
Gradle 依赖：
// Add this to your build.gradle
// No external dependencies needed for this implementation
这三种方式分别演示了不同的层序遍历实现方式：基于队列的迭代、基于递归的迭代和基于 Java 8 Stream 的现代实现。您可以根据项目的需求和个人偏好选择适合的实现方式。
