👨?💻博客主页:@花无缺
欢迎 点赞👍 收藏? 留言📝 加关注?!
本文由 花无缺 原创收录于专栏 【力扣题解】
给定两个整数数组 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万字详解】
你们的点赞👍 收藏? 留言📝 关注?
是我持续创作,输出优质内容
的最大动力!
谢谢!