题目：
106. Construct Binary Tree from Inorder and Postorder Traversa(medium)
解题思路：
根据定义，每次从后序中取出根节点，找出根节点在中序中的位置，递归处理。
难点在下一次递归函数中的左右下标位置。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23public TreeNode buildTree(int[] inorder, int[] postorder) {
if(inorder == null || postorder == null
|| inorder.length <= 0 || postorder.length <= 0
|| inorder.length != postorder.length) return null;
return construct(0,inorder.length-1,inorder,0,postorder.length-1,postorder);
}
private TreeNode construct(int ml,int mr,int[] mid,int postl,int postr,int[] post){
TreeNode root = new TreeNode(post[postr]);
if(postl == postr && ml == mr) return root;
int index = mr;//找中序中根结点的位置
while(root.val != mid[index] && index >= ml){
index--;
}
int rightcount = mr - index;
if(rightcount > 0)//右侧
root.right = construct(index+1,mr,mid, postr-rightcount,postr-1,post);
if(rightcount < mr - ml)//左侧
root.left = construct(ml,index-1,mid, postl,postr-rightcount-1 ,post);
return root;
}
