树的层次遍历是指按层次顺序访问树中所有节点的遍历方式。具体的步骤如下:
- 从根节点开始,将根节点入队。
- 进行循环,直到队列为空:
- 弹出队列中的节点,并访问该节点。
- 将该节点的所有子节点依次入队。
- 完成遍历。
层次遍历的相关知识点:
- 队列:层次遍历需要使用一个队列来暂存节点。每次访问一个节点时,将其子节点依次入队,并在下次循环时取出队首节点进行访问。
- 循环:层次遍历需要进行循环操作,直到队列为空时结束。循环过程中,不断将节点入队和出队,直到遍历完所有节点。
- 节点的访问:访问节点可以根据需求来确定,可以是打印节点的值,也可以是进行其他操作。
- 子节点入队:层次遍历需要将每个节点的所有子节点依次入队,以便在之后的循环中继续访问。
思路:
- 首先,创建一个队列,并将根节点入队。
- 进行循环,直到队列为空:
- 弹出队列中的节点,并访问该节点。
- 将该节点的所有子节点依次入队。
- 完成遍历。
这个思路是通过使用队列来实现层次遍历的关键。每次将节点出队并访问后,将其子节点入队,这样就保证了按层次顺序进行访问。
例题:
给你二叉树的根节点 root
,返回其节点值的 层序遍历 。 (即逐层地,从左到右访问所有节点)。
示例 1:
输入:root = [3,9,20,null,null,15,7] 输出:[[3],[9,20],[15,7]]
示例 2:
输入:root = [1] 输出:[[1]]
示例 3:
输入:root = [] 输出:[]
// 层序遍历二叉树并返回结果列表
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> lists = new ArrayList<>(); // 用于存储层序遍历结果的列表
Queue<TreeNode> queue = new LinkedList<>(); // 辅助队列,用于层序遍历
if (root == null) {
return new ArrayList<List<Integer>>(); // 如果根节点为空,直接返回空列表
}
queue.add(root); // 将根节点加入队列
while (!queue.isEmpty()) {
int size = queue.size(); // 当前层的节点数
List<Integer> list = new ArrayList<>(); // 用于存储当前层节点值的列表
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll(); // 出队列
list.add(node.val); // 将节点值加入当前层列表
// 将当前节点的左右子节点加入队列,以便遍历下一层
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
lists.add(list); // 将当前层的节点值列表加入最终结果列表
}
return lists; // 返回层序遍历结果列表
}
标签:遍历,层次,队列,queue,入队,root,节点
From: https://blog.csdn.net/wudi6688/article/details/140340727