106. 从中序与后序遍历序列构造二叉树【中等】
题解 递归参照105. 从前序与中序遍历序列构造二叉树的代码
class Solution {
private MapindexMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n=inorder.length;
indexMap=new HashMap<>();
for(int i=0;i
indexMap.put(inorder[i],i);
}
return buildTree(inorder,postorder,0,n-1,0,n-1);
}
public TreeNode buildTree(int[] inorder, int[] postorder,int inLeft,int inRight,int postLeft,int postRight){
if(inLeft>inRight)
return null;
int postRoot=postRight;//后序的根在数组的位置
int inRoot=indexMap.get(postorder[postRoot]);//中序的根在数组的位置
int leftTreeSize=inRoot-inLeft;//左子树结点数目
TreeNode root=new TreeNode(postorder[postRoot]);
root.left=buildTree(inorder,postorder,inLeft,inRoot-1,postLeft,postLeft+leftTreeSize-1);
root.right=buildTree(inorder,postorder,inRoot+1,inRight,postLeft+leftTreeSize,postRoot-1);
return root;
}
}
改进
由于在后序遍历序中每次最后一个结点都是子树的根,因此直接用一个指针控制后序遍历的结点位置即可
class Solution {
private int post_idx;
private MapindexMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
int n=inorder.length;
post_idx=n-1;//后序的根
indexMap=new HashMap<>();
for(int i=0;i
indexMap.put(inorder[i],i);
}
return buildTree(inorder,postorder,0,n-1);
}
public TreeNode buildTree(int[] inorder, int[] postorder,int inLeft,int inRight){
if(inLeft>inRight)
return null;
int inRoot=indexMap.get(postorder[post_idx]);//中序的根在数组的位置
TreeNode root=new TreeNode(postorder[post_idx]);
post_idx--;
//后序是左右根,所以倒着来的话应该先构建右子树再构建左子树
root.right=buildTree(inorder,postorder,inRoot+1,inRight);
root.left=buildTree(inorder,postorder,inLeft,inRoot-1);
return root;
}
}
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( n ) O(n) O(n)



