# 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);
    }
};