二叉树的层序遍历Java
时间: 2023-11-05 22:56:02 浏览: 40
二叉树的层序遍历是一种逐层地从左到右访问所有节点的方法。在Java中,可以使用递归或队列来实现二叉树的层序遍历。
递归方法的实现如下所示:
```java
public List<List<String>> levelOrder(Tree root) {
List<List<String>> list = new ArrayList<>();
levelOrderHelper(root, list, 0);
return list;
}
public void levelOrderHelper(Tree root, List<List<String>> list, int level) {
if (root == null) {
return;
}
if (level >= list.size()) {
list.add(new ArrayList<>());
}
list.get(level).add(root.val);
levelOrderHelper(root.left, list, level + 1);
levelOrderHelper(root.right, list, level + 1);
}
```
另一种方法是使用队列来实现,具体代码如下所示:
```java
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int len = queue.size();
List<Integer> list = new ArrayList<>();
while (len > 0) {
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
len--;
}
result.add(list);
}
return result;
}
```
以上是二叉树的层序遍历的两种Java实现方法。<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Java:实现二叉树的层次遍历](https://blog.csdn.net/qq_45000317/article/details/123143184)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
- *2* *3* [二叉树层序遍历——java](https://blog.csdn.net/weixin_50616848/article/details/124769746)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v92^chatsearchT3_1"}}] [.reference_item style="max-width: 50%"]
[ .reference_list ]