原题
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/ \
9 20
/ \
15 7
解法
思想
根据后序遍历最后一个元素是根、中序遍历以根为中心划分左子树和右子树的特点，递归构造左子树和右子树。
代码
我们逐渐来优化时间复杂度：
第一版，较好懂：
class Solution {
public int indexOf(int target,int[] order){
for(int i = 0;i<order.length;i++){
if(order[i] == target) return i;
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
if(postorder.length == 0) return null;
TreeNode root = getUnit(inorder,postorder);
return root;
}
public TreeNode getUnit(int[] inorder,int[] postorder){
if(postorder.length == 0) return null;
TreeNode root = new TreeNode(postorder[postorder.length-1]);
int index = indexOf(postorder[postorder.length-1],inorder);
int[] leftpartInorder = Arrays.copyOfRange(inorder,0,index);
int[] rightpartInorder = Arrays.copyOfRange(inorder,index+1,inorder.length);
int leftCount = leftpartInorder.length;
int[] leftpartPostorder = Arrays.copyOfRange(postorder,0,leftCount);
int[] rightpartPostorder = Arrays.copyOfRange(postorder,leftCount,postorder.length-1);
root.left = getUnit(leftpartInorder,leftpartPostorder);
root.right = getUnit(rightpartInorder,rightpartPostorder);
return root;
}
}
第二版，不用再复制数组，直接在原数组上操作：
class Solution {
int[] inorderGlobal;
int[] postorderGlobal;
public int indexOf(int target,int start,int end){
for(int i = 0;i<end-start;i++){
if(inorderGlobal[i+start] == target) return i+start;
}
return -1;
}
public TreeNode buildTree(int[] inorder, int[] postorder) {
inorderGlobal = inorder;
postorderGlobal = postorder;
if(postorder.length == 0) return null;
TreeNode root = getUnit(0,inorder.length,0,postorder.length);
return root;
}
public TreeNode getUnit(int inorderStart,int inorderEnd,int postorderStart,int postorderEnd){
if(postorderEnd==postorderStart) return null;
TreeNode root = new TreeNode(postorderGlobal[postorderEnd-1]);
int index = indexOf(postorderGlobal[postorderEnd-1],inorderStart,inorderEnd);
int leftCount = index-inorderStart;
root.left = getUnit(inorderStart,index,postorderStart,leftCount+postorderStart);
root.right = getUnit(index+1,inorderEnd,postorderStart+leftCount,postorderEnd-1);
return root;
}
}
第三版，既然经常要用查找元素在中序遍历中的位置，可以不需要使用indexOf函数，而是一开始则将对应关系保存在哈希表中：
class Solution {
int[] postorderGlobal;
Map<Integer,Integer> map;
public TreeNode buildTree(int[] inorder, int[] postorder) {
postorderGlobal = postorder;
map = new HashMap<>();
for(int i = 0;i < inorder.length; i++) map.put(inorder[i], i);
if(postorder.length == 0) return null;
TreeNode root = getUnit(0,inorder.length,0,postorder.length);
return root;
}
public TreeNode getUnit(int inorderStart,int inorderEnd,int postorderStart,int postorderEnd){
if(postorderEnd==postorderStart) return null;
TreeNode root = new TreeNode(postorderGlobal[postorderEnd-1]);
int index = map.get(postorderGlobal[postorderEnd-1]);
int leftCount = index-inorderStart;
root.left = getUnit(inorderStart,index,postorderStart,leftCount+postorderStart);
root.right = getUnit(index+1,inorderEnd,postorderStart+leftCount,postorderEnd-1);
return root;
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode106-%e4%bb%8e%e4%b8%ad%e5%ba%8f%e4%b8%8e%e5%90%8e%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/
