# Construct Binary Tree from Inorder and Postorder Traversal

> Given inorder and postorder traversal of a tree, construct the binary tree.

```
1
--------|-------
2 3
----|---- ----|----
4 5 6 7
```

+ 前序遍历 1245367
+ 中序遍历 4251637
+ 后续遍历 4526731

```c++
class Solution {
public:
unordered_map m;
TreeNode *buildTree(vector &inorder, vector &postorder) {
if(postorder.empty()) {
return NULL;
}

for(int i = 0; i < inorder.size(); i++) {
m[inorder[i]] = i;
}

return build(inorder, 0, inorder.size() - 1,
postorder, 0, postorder.size() - 1);
}

TreeNode* build(vector& inorder, int s0, int e0,
vector& postorder, int s1, int e1) {
if(s0 > e0 || s1 > e1) {
return NULL;
}

TreeNode* root = new TreeNode(postorder[e1]);

int mid = m[postorder[e1]];
int num = mid - s0;

root->left = build(inorder, s0, mid - 1, postorder, s1, s1 + num - 1);
root->right = build(inorder, mid + 1, e0, postorder, s1 + num, e1 - 1);

return root;
}
};
```

# Construct Binary Tree from Preorder and Inorder Traversal

> Given preorder and inorder traversal of a tree, construct the binary tree.

+ 通过前序遍历找到根节点
+ 通过根节点将中序遍历数据拆分成两部分
+ 对于各个部分重复上述操作

```c++
class Solution {
public:
unordered_map m;
TreeNode *buildTree(vector &preorder, vector &inorder) {
if(preorder.empty()) {
return NULL;
}

for(int i = 0; i < inorder.size(); i++) {
m[inorder[i]] = i;
}

return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
}

TreeNode* build(vector& preorder, int s0, int e0, vector &inorder, int s1, int e1) {
if(s0 > e0 || s1 > e1) {
return NULL;
}

int mid = m[preorder[s0]];

TreeNode* root = new TreeNode(preorder[s0]);

int num = mid - s1;

root->left = build(preorder, s0 + 1, s0 + num, inorder, s1, mid - 1);
root->right = build(preorder, s0 + num + 1, e0, inorder, mid + 1, e1);

return root;
}
};
```