原题
根据一棵树的前序遍历与中序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解法
思想
根据前序遍历第一个元素是根、中序遍历以根为中心划分左子树和右子树的特点，递归构造左子树和右子树。
算法优化过程见：leetcode106-从中序与后序遍历序列构造二叉树
代码
class Solution {
int[] preorderGlobal;
Map<Integer,Integer> map;
public TreeNode buildTree(int[] preorder, int[] inorder) {
preorderGlobal = preorder;
map = new HashMap<>();
for(int i = 0;i < inorder.length; i++) map.put(inorder[i], i);
if(preorder.length == 0) return null;
TreeNode root = getUnit(0,preorder.length,0,inorder.length);
return root;
}
public TreeNode getUnit(int preorderStart,int preorderEnd,int inorderStart,int inorderEnd){
if(preorderStart==preorderEnd) return null;
TreeNode root = new TreeNode(preorderGlobal[preorderStart]);
int index = map.get(preorderGlobal[preorderStart]);
int leftCount = index - inorderStart;
root.left = getUnit(preorderStart+1,preorderStart+leftCount+1,inorderStart,index);
root.right = getUnit(preorderStart+leftCount+1,preorderEnd,index+1,inorderEnd);
return root;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode105-%e4%bb%8e%e5%89%8d%e5%ba%8f%e4%b8%8e%e4%b8%ad%e5%ba%8f%e9%81%8d%e5%8e%86%e5%ba%8f%e5%88%97%e6%9e%84%e9%80%a0%e4%ba%8c%e5%8f%89%e6%a0%91/
