题目描述:
给定两个整数数组 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
保证 为二叉树的中序遍历序列
解题准备:
1.了解二叉树:二叉树是递归定义的,当其根节点root!=null时,它有以下性质:root有且仅有两颗子树,分别是左子树left和右子树right。如果把left看成树(left!=null,不过实际也是一棵树),那么其左子树也是一棵二叉树,同理,右子树right也是。
2.了解二叉树前序、中序遍历:二叉树DFS深度优先算法有前序、中序和后序三种,其“序”的概念针对于根节点root。对于前序:root->left->right,也就是根节点、左子树、右子树;对于中序:即左子树、根节点、右子树。
3.猜测可能存在的基础操作:由于需要构造二叉树,而且提供的是两个数组(前序遍历数组、中序遍历数组),所以大概率需要进行“添加”这一基础操作(勉强算是吧)。由于提供只两个数组,感觉可能要遍历。。所以初步认为可能有遍历、添加两个基础操作。
4.模拟操作:
对于下图的二叉树,我们可能轻松得到其前序、中序遍历数组(当然了,这是输入,是已知条件)
那好像看不出什么操作:从定义开始,先寻找一下两个数组的关系。
解题难点1分析:
难点1:如何分步操作,构造这棵二叉树?
从定义出发,我们知道:
1.前序数组是:【根节点,左子树,右子树】
2.中序数组是:【左子树,根节点,右子树】
那么,我们可以通过二者的相互关系,得到左子树前序、中序遍历数组。
可是好像没什么用?拿到左子树的遍历数组(把它当成独立的树),好像又回到原来的问题:怎么分步构造树?
我们知道,在左子树前、中序遍历中,一定也存在根节点,并且在前序遍历中,第一个节点就是根节点。
那,这个性质怎么用?
我们先了解两件事:
1.二叉树由递归构造。
2.对于一棵树,其所有基础操作都要落到具体的节点上,如果拿不到具体节点,什么都是假的。
我们认为题目提供的函数已经具备构造二叉树的能力。
也就是说,既然题目提供了前序、中序数组就能得到二叉树,不如我们借助递归去利用这个函数。
因此,对于树root、left、right,我们把left的前、中序遍历数组,作为函数参数传递。
不过问题来了:传递了第一遍,就没法拿到左子树left的左子树了。而且另一个问题是,前序、中序数组的构造也是个麻烦,每一个节点的左、右子树的长度不一定一样。
也许是缺参数了,如果我们可以提供左、右子树的长度,在进行传递,就可以了?
不行,这一步反而陷入重复论证,因为我们如果可以构造一个左子树(或右子树)数组,那么就一定知道其长度。(left.length)。
不过我们记得:二叉树递归定义,所以其前序、中序遍历也具有递归性,对于左子树的前序遍历序列,有:
left:【根节点left,left的左子树,left的右子树】
把它放进根节点root中,有:【root,【(左子树)left,left左子,left右子】,右子树同理】
也就是说,题目提供的前序、中序遍历数组,其中就包含了某个节点的前、中序遍历。
所以,我们的问题就转换为:如何从题目提供的数组中,拿到某个节点的前、中序遍历。
通过双指针(指向数组)就可以了,既然其具有递归性,那么某个节点的前、中序遍历是连续的(我指的是,数组中的元素连续,比如【1,2,3,4,5】,“1,2,3”连续,“1,3”不连续)
对前序数组,用一个双指针,对中序数组,再用一个双指针,一共4个变量,就可以覆盖数据。
因此,我们的新函数X,需要6个参数,前、中序遍历数组,4个指针。
不过问题又来了:要怎么构造树呢?
我们已经可以针对某个节点,得到其前、中序遍历,那么,就可以一直递归到该节点是叶子节点的时候。
对于某个节点A,A如果是叶子节点,那么它返回其本身即可。
A如果有子树,那么需要把子树连接到其确定位置。
对于函数X,我们认为其具备构造二叉树的能力,只要提供给X一棵树的前、中序遍历,X就可以返回这棵树的根节点。
因此,A有子树,如果是左子树,把左子树的前、中序遍历提供给X,然后A.left=X()即可。
右子树同理。
那么,如何拿到左右子树?
1.前序:根、左、右,第一个一定是根。
2.中序:左、根、右,拿到根,就可确定左、右子树(的长度),然后……
由于数组不存在重复元素,所以不会出错。
如果从前序拿到根,然后在中序中遍历,速度较慢,可以用哈希表。
代码:
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {Map<Integer, Integer> index; // 这里需要注意,如果没写泛型,默认为object,可能出错public TreeNode buildTree(int[] preorder, int[] inorder) {index=new HashMap<Integer, Integer>();int n=inorder.length;for(int i=0; i<n; i++){index.put(inorder[i], i); // 提供一个快速搜索的方式,用数组搜索也一样。}return myBuild(preorder, inorder, 0, n-1, 0, n-1);}// 递归调用private TreeNode myBuild(int[] preorder, int[] inorder, int pre_left,int pre_right, int in_left, int in_right){// 叶子节点,因为叶子节点的前、中序遍历数组为nullif(pre_right<pre_left){return null;}int root_val=preorder[pre_left]; // 得到根节点的值 int in_root=index.get(root_val); // 从中序遍历数组,拿到根节点下标int len=in_root-in_left; // 拿到节点A的遍历数组的长度TreeNode root=new TreeNode(root_val); // 实例化根节点(该根节点并非题解的根节点)root.left=myBuild(preorder, inorder, pre_left+1, pre_left+len,in_left, in_root-1); // 递归调用,前序遍历第一个是根节点,所以加1,加len是因为前、中序遍历长度相同,由于中序先是左子树,所以从left到根节点-1root.right=myBuild(preorder, inorder, pre_left+len+1, pre_right,in_root+1, in_right); // 递归调用,想拿到右子树,那么得从左子树末尾开始,后面都是右子树,所以是pre_right。中序是左根右,所以从根+1到in_rightreturn root;}
}
以上内容即我想分享的关于力扣热题11的一些知识。
我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。