左神的讲解
给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，请构造二叉树并返回其根节点
前序遍历[3,9,20,15,7]中序遍历[9,3,15,20,7]
从中序遍历中找到头节点的位置find，在前序遍历的结果中把左右子树分开。关键点是怎么分？一不留神就容易出错，左神的方法：化抽象为具体，随便找几个数
中序：假设find为位置在1那么左子树有3个数，位置为13,14,1对应在前序遍历的结果中也会有三个数，位置为81111118L、、、、、find、、、R2
前序：左子树的左边界为L1+1=右边界为L1+3=8；易错点：3如何得到？答案是find-L所以左子树的右边界为L1+find-L2；10L、、、|、、、、R1
递归的参数：左子树：前序遍历的左边界L1+1,右边界L1+find-L2,中序遍历的左边界L右边界find-root.left=recur;
右子树：前序遍历的左边界L1+find-L2+右边界R1中序遍历的左边界find+右边界R2root.right=recur;
上代码
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length != inorder.length){
return null;
}
return recur(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1);
}
TreeNode recur(int[]preorder,int L1,int R1,int[] inorder,int L2,int R2){
if(L1 > R1){
return null;
}
//根节点建出来
TreeNode root = new TreeNode(preorder[L1]);
//如果只有一个节点，返回这个节点
if(L1 == R1){
return root;
}
//前序遍历第一个节点就是头，要从中序遍历中找到头节点，把中序结果分为左子树和右子树
int find = L2;
while(inorder[find] != preorder[L1]){
find ++;
}
//前序遍历左子树的范围L1+1,L1+find-L2,中序遍历左子树的范围L2,find-1，
root.left = recur(preorder,L1+1,L1+find-L2,inorder,L2,find-1);
//前序遍历右子树的范围L1+find-L2+1,R1,中序遍历右子树的范围find+1,R2，
root.right = recur(preorder,L1+find-L2+1,R1,inorder,find+1,R2);
return root;
}
}
优化做法：把中序数组和下标用哈希表存起来，使用的时候直接拿过来用，不用再去遍历查找，空间换时间
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || inorder == null || preorder.length != inorder.length){
return null;
}
//把中序遍历的结果放入hashmap中，用的时候直接拿过来用，不用去遍历中序数组，空间换时间
Map<Integer,Integer> valueMap = new HashMap<>();
for(int i = 0;i < inorder.length;i ++){
valueMap.put(inorder[i],i);
}
return recur(preorder,0,preorder.length - 1,inorder,0,inorder.length - 1,valueMap);
}
TreeNode recur(int[]preorder,int L1,int R1,int[] inorder,int L2,int R2,Map<Integer,Integer> valueMap){
if(L1 > R1){
return null;
}
//根节点建出来
TreeNode root = new TreeNode(preorder[L1]);
//如果只有一个节点，返回这个节点
if(L1 == R1){
return root;
}
//前序遍历第一个节点就是头，要从中序遍历中找到头节点，把中序结果分为左子树和右子树
// int find = L2;
// while(inorder[find] != preorder[L1]){
// find ++;
// }
//空间换时间的做法
int find = valueMap.get(preorder[L1]);
//前序遍历左子树的范围L1+1,L1+find-L2,中序遍历左子树的范围L2,find-1，
root.left = recur(preorder,L1+1,L1+find-L2,inorder,L2,find-1,valueMap);
//前序遍历右子树的范围L1+find-L2+1,R1,中序遍历右子树的范围find+1,R2，
root.right = recur(preorder,L1+find-L2+1,R1,inorder,find+1,R2,valueMap);
return root;
}
}
文章为作者独立观点，不代表 股票程序化软件自动交易接口观点
相关文章
股民评论