# LeetCode – Construct Binary Tree from Inorder and Postorder Traversal

### 题目：

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

Note:
You may assume that duplicates do not exist in the tree.

For example, given

```inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]```

Return the following binary tree:

```    3
/ \
9  20
/  \
15   7```

### 实现：

• 递归方式，根据二叉树中序遍历和后续遍历，创建二叉树。中序遍历： 左-根-右， 后续遍历： 左-右-根， 所以可以通过后续遍历的最后一个节点找到根节点，并生成根节点， 因为二叉树没有重复节点， 就 可以在中序遍历数据中找到根节点，再分成左右两个子树，递归执行下去，遍历完所有节点。 通过postorder获取根节点， 通过inorder生成左右子树，查找节点在中序遍历数据组里位置，可以通过unordered_map实现。
• 不使用map情况下   时间复杂度 O(N^2)    , 使用map查找O(N)
``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
unordered_map <int, int> treemap;
for (int i=0; i<inorder.size();i++) {
treemap[inorder[i]] = i;
}
int index = inorder.size()-1;
return  helper(inorder, postorder, 0, inorder.size()-1, &index, treemap);
}
TreeNode *helper(vector<int> & inorder, vector<int>& postorder, int left, int right,
int *index , unordered_map<int, int>&treemap){
//check
if (left > right){
return NULL;
}

// create root  node
/* destory postorder vector
int val = postorder.back();
TreeNode *node = new TreeNode(val);
postorder.pop_back();
*/
int val = postorder[*index];
TreeNode *node = new TreeNode(val);
(*index)--;

// search inorder by array
/*
int root = -1;
for (int i=left ; i <=right; i ++){
if (val == inorder[i]){
root = i;
break;
}
}
if (root == -1){
return node;
}*/
// search inorder by map
int root = treemap[val];

// create left & right node
node->right = helper(inorder, postorder,  root+1, right, index,  treemap);
node->left  = helper(inorder, postorder, left, root-1, index, treemap);

return node;
}
};``````