【力扣题解】P105-从前序与中序遍历序列构造二叉树-Java题解
2023-12-30 16:31:19
👨?💻博客主页:@花无缺
欢迎 点赞👍 收藏? 留言📝 加关注?!
本文由 花无缺 原创收录于专栏 【力扣题解】
【力扣题解】P105-从前序与中序遍历序列构造二叉树-Java题解
🌏题目描述
给定两个整数数组 preorder
和 inorder
,其中 preorder
是二叉树的先序遍历, inorder
是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:
输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000
inorder.length == preorder.length
-3000 <= preorder[i], inorder[i] <= 3000
preorder
和inorder
均 无重复 元素inorder
均出现在preorder
preorder
保证 为二叉树的前序遍历序列inorder
保证 为二叉树的中序遍历序列
💡题解
public static TreeNode buildTree(int[] preorder, int[] inorder) {
// 空树
if (preorder.length == 0) {
return null;
}
// 根节点
int rootValue = preorder[0];
// 构造树
TreeNode root = new TreeNode(rootValue);
// 只有一个节点, 直接返回树
if (preorder.length == 1) {
return root;
}
// 在中序数组中查找当前节点(根节点)值的索引
int divideIndex = 0;
for (; divideIndex < inorder.length; divideIndex++) {
if (inorder[divideIndex] == rootValue) {
break;
}
}
// 根据当前节点的索引切割中序数组
// 左子数组的元素就是二叉树左子树的所有节点
// 右子数组的元素就是二叉树右子树的所有节点
int[] leftInorder = Arrays.copyOfRange(inorder, 0, divideIndex);
int[] rightInorder = Arrays.copyOfRange(inorder, divideIndex + 1, inorder.length);
// 分割前序数组
// 先移除前序数组的最后一个元素(当前节点/根节点), 因为根节点的值我们已经使用了
preorder = Arrays.copyOfRange(preorder, 1, preorder.length);
// 然后根据切割后的中序左右数组的长度切割后序数组
// 因为中序数组和后序数组对应的长度都是相等的
int[] leftPreorder = Arrays.copyOfRange(preorder, 0, divideIndex);
int[] rightPreorder = Arrays.copyOfRange(preorder, divideIndex, preorder.length);
// 递归构造左子节点和右子节点
root.left = buildTree(leftPreorder, leftInorder);
root.right = buildTree(rightPreorder, rightInorder);
// 返回根节点
return root;
}
时间复杂度:O(n)
,二叉树有 n 个节点,需要递归 n 次递归函数。
🌏总结
由二叉树的性质我们可以知道,如果知道一个二叉树的中序与前序序列,那么我们是可以还原这棵二叉树的,那么具体怎么还原呢?二叉树的前序序列的第一个元素就是二叉树的根节点值,然后根节点值在中序序列中是在序列的中间,左右两边分别是左子树和右子树的所有节点值,所以我们使用递归,每次在前序序列中找到当前子树的根节点,使用根节点构建树,然后根据根节点将中序序列分为两个子数组,分别代表当前节点(根节点)的左右子树,而中序序列和前序序列对应的子树的序列长度是相同的,所以我们可以根据中序序列的子数组再将前序序列分为两个子数组,然后根据分开后的四个子数组递归地构建当前节点的左右子节点,就可以还原这棵二叉树。
🌸欢迎
关注
我的博客:花无缺-每一个不曾起舞的日子都是对生命的辜负~
🍻一起进步-刷题专栏:【力扣题解】
🥇往期精彩好文:
📢【CSS选择器全解指南】
📢【HTML万字详解】
你们的点赞👍 收藏? 留言📝 关注?
是我持续创作,输出优质内容
的最大动力!
谢谢!
文章来源:https://blog.csdn.net/huawuque404/article/details/135306018
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!