# [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.

```// in inorder traversal sequence, the nodes are organized as [left] [root] [right]
// in postorder traversal sequence, the nodes are organized as [left] [right] [root]
// construct the original tree recursively.
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return _buildTree(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
}
TreeNode * _buildTree(vector<int>::iterator inorderStart, vector<int>::iterator inorderEnd, vector<int>::iterator postorderStart, vector<int>::iterator postorderEnd){
//base condition
if(inorderStart == inorderEnd){
return NULL;
}
int vRoot = *(postorderEnd - 1);
int i = 0;
while(*(inorderStart + i) != vRoot){
i++;
}
TreeNode * root = new TreeNode(vRoot);
root->left = _buildTree(inorderStart, inorderStart + i, postorderStart, postorderStart + i);
root->right = _buildTree(inorderStart + i + 1, inorderEnd, postorderStart + i, postorderEnd - 1);
return root;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.