根據中序遍歷和后序遍歷樹構造二叉樹
給出樹的中序遍歷: [1,2,3] 和后序遍歷: [1,3,2]
返回如下的樹:
2
/ \
1 3
**規則**
輸入:兩個數組 int a[] 和 int b[]
輸出:頭結點Head
case:
```
數組為null或length為0
兩個數組長度不一致,內容不同
只有一個元素
只有兩個元素
都在左側
都在右側
兩邊都有
```
**思路**
對一個實例`[4,7,2,1,5,3,8,6][7,4,2,5,8,6,3,1]`進行分析后,可以得出這樣的規則
```
b[len-1]為頭節點,該節點為1,在pre中查找1的位置為pos=3,從pos=3開始,共3個元素為左邊子樹,4-end為右邊子樹
設每次數組有范圍ae~ab be-bb mid為post[bb-1]在pre中的位置
左 ab = ab ae = mid-1 bb = bb be = bb+(mid-1-ab) (be-bb = ae -ab)
右 ab = mid+1 ae=ae bb=(be-1)-(ae-mid-1) be=be-1
其中,ae不能大于ab be不能大于bb 否則返回null
```
**代碼**
```
public class Solution {
/*
* @param inorder: A list of integers that inorder traversal of a tree
* @param postorder: A list of integers that postorder traversal of a tree
* @return: Root of a tree
*/
public TreeNode buildTree(int[] preorder, int[] postorder) {
if(preorder == null || postorder == null) {return null;}
if(preorder.length * postorder.length == 0) {return null;}
if(preorder.length != postorder.length) {return null;}
return buildTree(preorder,0,preorder.length-1,postorder,0,postorder.length-1);
}
private TreeNode buildTree (int[] pre,int ab,int ae, int[] post,int bb,int be) {
if(ab > ae || bb > be) return null;
int p = post[be],mid = 0;
for ( mid = ab; mid <= ae; mid++) {
if(pre[mid] == p) {
break;
}
}
// FIND MID
TreeNode node = new TreeNode(p);
node.left = buildTree(pre,ab,mid-1,post,bb,bb+(mid-1-ab+1)-1);
node.right = buildTree(pre,mid+1,ae, post,(be-1)-(ae-mid-1),be-1);
return node;
}
}
```