二叉树的层次遍历java
时间: 2023-09-04 16:04:23 浏览: 62
### 回答1:
// Definition for a binary tree node.
// public class TreeNode {
// int val;
// TreeNode left;
// TreeNode right;
// TreeNode() {}
// TreeNode(int val) { this.val = val; }
// TreeNode(int val, TreeNode left, TreeNode right) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root); // 将根节点加入队列
while (!queue.isEmpty()) {
int levelSize = queue.size(); // 获取当前层的节点数
List<Integer> currLevel = new ArrayList<>(); // 当前层的节点值列表
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
currLevel.add(node.val); // 将节点值加入列表
if (node.left != null) queue.offer(node.left); // 将左子节点加入队列
if (node.right != null) queue.offer(node.right); // 将右子节点加入队列
}
res.add(currLevel); // 将当前层的节点值列表加入结果列表
}
return res;
}
}
### 回答2:
二叉树的层次遍历是一种广度优先搜索(BFS)的算法。这种算法从根节点开始逐层遍历,并按照从上到下、从左到右的顺序访问每个节点。
在Java中,我们可以使用队列来实现二叉树的层次遍历。
首先,我们需要定义一个辅助队列来存储待遍历的节点。开始时,将根节点入队。
接下来,我们使用一个循环来迭代访问队列中的节点,直到队列为空。在每一轮迭代中,我们取出队列的头部节点,将其值存储起来,并访问其左右子节点(如果存在),然后将子节点依次入队。
具体的代码实现如下:
```java
public void levelOrderTraversal(TreeNode root) {
if (root == null) {
return;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val + " ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
}
```
以上代码中,先判断根节点是否为空,若为空则直接返回。然后定义一个队列queue,并将根节点入队。
接下来,进入while循环,判断队列是否为空。若不为空,则将队列的头部节点出队,并打印其值。
然后,判断当前节点的左右子节点,若存在则将它们依次入队。
最终,当队列为空时,表示层次遍历已经完成。
通过以上步骤,就可以实现二叉树的层次遍历。
### 回答3:
二叉树的层次遍历是通过逐层遍历二叉树节点的算法。在层次遍历中,我们从根节点开始,逐层遍历直到叶子节点。层次遍历的顺序是从左到右,一层一层地进行。
在Java中,我们可以使用队列来实现二叉树的层次遍历。首先,我们将根节点入队列,然后进入循环。在循环中,我们取出队列中的一个节点,并进行相应的处理,比如输出节点的值。接下来,将该节点的左孩子和右孩子分别入队列。然后继续循环,直到队列为空。
下面是一个示例代码:
```java
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public void levelOrderTraversal(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);
}
}
}
```
以上是二叉树层次遍历的Java实现。我们使用队列来保存待遍历的节点,每次从队列中取出一个节点并输出其值,然后将其左孩子和右孩子入队列。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)