层序便利二叉树的递归实现java
时间: 2024-08-13 11:01:11 浏览: 32
层序遍历二叉树,也称为广度优先遍历(BFS),通常采用队列数据结构配合迭代的方式实现。然而,在 Java 中实现层序遍历时可以利用递归来模拟队列的操作,通过传递一个额外的参数(即当前层级)来记录当前节点所在层次。
下面是层序遍历二叉树的递归实现示例:
```java
import java.util.*;
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
traverse(root, 0, result);
return result;
}
private void traverse(TreeNode node, int level, List<List<Integer>> result) {
if (node == null) {
return;
}
// 如果结果集中的层数小于等于当前层级,则添加新的一层列表
if (result.size() <= level) {
result.add(new ArrayList<>());
}
// 将当前节点值加入到对应的层级列表
result.get(level).add(node.val);
// 分别对左右子节点进行深度优先搜索,并增加一层深度
traverse(node.left, level + 1, result);
traverse(node.right, level + 1, result);
}
```
### 函数解释:
- `levelOrder` 函数接收根节点作为输入,返回一个二维列表,其中每个一维列表表示一层的节点值。
- `traverse` 函数是一个递归函数,它接受当前节点、当前层次以及结果列表作为输入。
- 当前节点为空时,返回终止条件。
- 检查结果列表是否包含当前层次的数据,如果不存在则添加新层。
- 将当前节点值添加至对应层级的列表中。
- 对左子节点和右子节点进行深度优先搜索,同时递增层次计数。
### 相关问题:
1. **如何判断一棵二叉树是否为满二叉树**?
2. **层序遍历除了递归外还有哪些实现方式**?
3. **如何实现二叉树的深度查找**?