Given two integer arrays inorder and postorder where inorder is the inorder traversal of a binary tree and postorder is the postorder traversal of the same tree, construct and return the binary tree.

&nbsp;
Example 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]


Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]


&nbsp;
Constraints:


	1 &lt;= inorder.length &lt;= 3000
	postorder.length == inorder.length
	-3000 &lt;= inorder[i], postorder[i] &lt;= 3000
	inorder and postorder consist of unique values.
	Each value of postorder also appears in inorder.
	inorder is guaranteed to be the inorder traversal of the tree.
	postorder is guaranteed to be the postorder traversal of the tree.


import bisect
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):

    def buildTree(self, inorder, postorder):
        """
        7
         2
       -8 
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: TreeNode
        ([-4,-10,3,-1], [7]) ((11,-8,2), [7])
        """
        currentSplits = [(inorder, [], [])]
        nodeDirectory = {}
        finalSplits = []
        for nodeVal in reversed(postorder):
            nodeDirectory[nodeVal] = TreeNode(nodeVal)
            for splits, nodes, directions in reversed(currentSplits):
                removing = None
                if nodeVal in splits:
                    removing = (splits, nodes, directions)
                    left = splits[:splits.index(nodeVal)]
                    right = splits[splits.index(nodeVal)+1:]
                    currentSplits.append((left, nodes+[nodeVal], directions + ['left']))
                    if len(left) <= 1:
                        finalSplits.append((left, nodes+[nodeVal], directions + ['left']))
                    currentSplits.append((right, nodes+[nodeVal], directions + ['right']))
                    if len(right) <= 1:
                        finalSplits.append((right, nodes+[nodeVal], directions + ['right']))
                    break
                if removing:
                    currentSplits.remove(removing)
        finalSplits = [splits for splits in finalSplits if splits[0]]

        while finalSplits:
            nodeVal, nodes, directions = finalSplits.pop()
            bottomNode = nodeDirectory[nodeVal[0]] if nodeVal else None
            while nodes:
                attachingNode = nodeDirectory[nodes.pop()]
                attachingDir = directions.pop()
                if attachingDir == 'left':
                    attachingNode.left = bottomNode
                else:
                    attachingNode.right = bottomNode
                bottomNode = attachingNode
        return nodeDirectory[postorder[-1]]
class Solution {
    int[] io; int[] po;
    int n;   // nth post order node 
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.n = inorder.length-1; this.io = inorder; this.po = postorder; 
        return buildTree(0, n); 
    }
    public TreeNode buildTree(int low, int high) {
        if(n < 0 || low > high) return null;
        int currNode = po[n--];
        int idxInInorder = low;
        TreeNode root = new TreeNode(currNode); 
        if(low == high) return root;   // no more nodes
        
        while(io[idxInInorder] != currNode) idxInInorder++; // find index of currNode in inorder
        root.right = buildTree(idxInInorder+1, high);
        root.left = buildTree(low, idxInInorder-1);
        return root;    
    }
}
class Solution {
public:
    TreeNode* buildTree(vector<int>& ino, vector<int>& post) {
    int i1 = post.size()-1;
        return solve(i1,ino,post,0,ino.size()-1);
    }
    TreeNode* solve(int &i,vector<int> &in,vector<int> &post,int l,int r){
        if(l>r)return NULL;
        int x = r;
        while(post[i] != in[x]){
            x--;
        }
        i--;
        // cout<<in[x]<<" ";
        TreeNode* root = new TreeNode(in[x]);
        root->right = solve(i,in,post,x+1,r);
        root->left = solve(i,in,post,l,x-1);
        return root;
    }
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    let postIndex = postorder.length - 1

    const dfs = (left, right) => {
        if (left > right) return null

        const val = postorder[postIndex--]
        const mid = inorder.findIndex(e => e === val)
        const root = new TreeNode(val)

        root.right = dfs(mid + 1, right)
        root.left = dfs(left, mid - 1)

        return root
    }

    return dfs(0, inorder.length - 1)
};
Construct Binary Tree from Inorder and Postorder Traversal