# 106. 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.
Example:
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]
Return the following binary tree:
3
/ \
9 20
/ \
15 7
# Solution
Approach 1: recursion.
# Code (Python)
Approach 1:
class Solution:
def buildTree(self, inorder, postorder):
"""
:type inorder: List[int]
:type postorder: List[int]
:rtype: TreeNode
"""
if not inorder:
return None
return self._build(inorder, 0, len(inorder) - 1, postorder, 0, len(inorder) - 1)
def _build(self, inorder, start1, end1, postorder, start2, end2):
if start1 > end1:
return None
if start1 == end1:
return TreeNode(inorder[start1])
root = TreeNode(postorder[end2])
len_left = inorder.index(root.val) - start1
root.left = self._build(inorder, start1, start1 + len_left - 1, postorder, start2, start2 + len_left - 1)
root.right = self._build(inorder, start1 + len_left + 1, end1, postorder, start2 + len_left, end2 - 1)
return root
# Code (C++)
Approach 1:
/**
* 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 {
private:
TreeNode* doBuildTree(vector<int>& inorder, int iHead, int iTail, vector<int>& postorder, int pHead, int pTail) {
if (iHead > iTail || pHead > pTail)
return NULL;
int i;
for (i = iHead; i <= iTail; ++i)
{
if (inorder[i] == postorder[pTail])
break;
}
int iLeftHead = iHead;
int iLeftTail = i - 1;
int iRightHead = i + 1;
int iRightTail = iTail;
int pLeftHead = pHead;
int pLeftTail = pLeftHead + (iLeftTail - iLeftHead);
int pRightHead = pLeftTail + 1;
int pRightTail = pTail - 1;
TreeNode *root = new TreeNode(postorder[pTail]);
root->left = doBuildTree(inorder, iLeftHead, iLeftTail, postorder, pLeftHead, pLeftTail);
root->right = doBuildTree(inorder, iRightHead, iRightTail, postorder, pRightHead, pRightTail);
return root;
}
public:
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
return doBuildTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}
};