在我给出的代码的基础上写
时间: 2024-10-08 18:20:05 浏览: 24
怎样写出好的单片机C语言代码
当然,基于您提供的代码片段,它包含了一个名为`Solution`的类,用于解决层序遍历的问题。我们已经有了一个`levelOrder`方法,用于接收前序遍历`preorder`和中序遍历`inorder`作为输入,并返回层序遍历的结果。接下来,我会扩展一些注释以便更好地理解代码的工作原理。
```java
// 定义TreeNode类,表示二叉树节点
class TreeNode {
int val;
TreeNode left;
TreeNode right;
// 构造函数
TreeNode(int x) {
val = x;
}
}
// 在Solution类中添加层序遍历的实现细节
public class Solution {
// 主方法 levelOrder,接受前序和中序遍历数组,返回层序遍历结果数组
public List<Integer> levelOrder(int[] preorder, int[] inorder) {
// 验证输入是否为空或长度为0
if (preorder == null || inorder == null || preorder.length == 0 || inorder.length == 0) {
return new ArrayList<>(); // 如果为空,则返回空列表
}
// 调用 buildTree 方法创建二叉树根节点
TreeNode root = buildTree(preorder, inorder);
// 如果根节点不存在,说明输入无效,返回空列表
if (root == null) {
return new ArrayList<>();
}
// 初始化空的层次遍历结果列表
List<List<Integer>> levelList = new ArrayList<>();
// 使用深度优先搜索 (DFS) 并记录每一层节点值
dfs(root, levelList);
// 返回层序遍历的第一个列表元素,即整个二叉树的层序序列
return levelList.get(0);
}
// 辅助方法 buildTree,根据前序遍历和中序遍历来构造二叉树
private TreeNode buildTree(int[] preorder, int[] inorder, int pStart, int pEnd, int iStart, int iEnd) {
// 确保遍历范围有效
if (pStart > pEnd || iStart > iEnd) {
return null;
}
// 获取前序遍历中的根节点值
int rootVal = preorder[pStart];
// 在中序遍历中查找根节点的位置
int inRootIndex = searchInOrder(inorder, iStart, iEnd, rootVal);
// 构建根节点
TreeNode root = new TreeNode(rootVal);
// 分别构建左子树和右子树
root.left = buildTree(preorder, inorder, pStart + 1, pStart + inRootIndex - iStart, iStart, inRootIndex - 1);
root.right = buildTree(preorder, inorder, pStart + inRootIndex - pStart + 1, pEnd, inRootIndex + 1, iEnd);
return root;
}
// 在中序遍历中查找目标值的索引
private int searchInOrder(int[] inorder, int start, int end, int target) {
// ... (这里可以参考之前的searchInOrder方法实现)
}
// 深度优先搜索辅助方法,用于添加节点到对应层数的列表
private void dfs(TreeNode node, List<List<Integer>> levelList, int depth) {
// ... (这里继续实现dfs方法)
}
}
```
在这个代码中,关键点包括:
1. **buildTree** 函数用于根据前序和中序遍历创建二叉树。
2. **searchInOrder** 函数用于寻找中序遍历中目标值的索引,帮助定位当前节点。
3. **dfs** 函数实现了递归的深度优先搜索,逐层添加节点到结果列表中。
阅读全文