Given two integer arrays, preorder and postorder where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

If there exist multiple answers, you can return any of them.

&nbsp;
Example 1:

Input: preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]


Example 2:

Input: preorder = [1], postorder = [1]
Output: [1]


&nbsp;
Constraints:


	1 &lt;= preorder.length &lt;= 30
	1 &lt;= preorder[i] &lt;= preorder.length
	All the values of preorder are unique.
	postorder.length == preorder.length
	1 &lt;= postorder[i] &lt;= postorder.length
	All the values of postorder are unique.
	It is guaranteed that preorder and postorder are the preorder traversal and postorder traversal of the same binary tree.


class Solution:
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:

        def build(preorder, preStart, preEnd, postorder, postStart, postEnd):
            if preStart > preEnd:
                return
            elif preStart == preEnd:
                return TreeNode(preorder[preStart])
            
            rootVal = preorder[preStart]
            leftRootVal = preorder[preStart + 1]
            index = valToIndex[leftRootVal]
            root = TreeNode(rootVal)
            leftSize = index - postStart + 1
            
            root.left = build(preorder, preStart + 1, preStart + leftSize,
postorder, postStart, index)
            root.right = build(preorder, preStart + leftSize + 1, preEnd,
postorder, index + 1, postEnd - 1)
            
            return root
        
        valToIndex = {}
        for i in range(len(postorder)):
            valToIndex[postorder[i]] = i
        
        return build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)
class Solution
{
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder)
    {
        // O(n) time | O(h) space
        if(preorder == null || postorder == null || preorder.length == 0 || postorder.length == 0) return null;

        TreeNode root = new TreeNode(preorder[0]);
        int mid = 0;

        if(preorder.length == 1) return root;

        // update mid
        for(int i = 0; i < postorder.length; i++)
        {
            if(preorder[1] == postorder[i])
            {
                mid = i;
                break;
            }
        }

        root.left = constructFromPrePost(
                                            Arrays.copyOfRange(preorder, 1, 1 + mid + 1),
                                            Arrays.copyOfRange(postorder, 0, mid + 1));

        root.right = constructFromPrePost(
                                            Arrays.copyOfRange(preorder, 1 + mid + 1, preorder.length),
                                            Arrays.copyOfRange(postorder, mid + 1, postorder.length - 1));
        return root;
    }
}
/**
 * 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:
    bool vis[40];
    
    TreeNode* solve(vector<int>& pre,int p, vector<int>& pos,int q){
        TreeNode* root=new TreeNode(pre[p]);
        vis[pre[p]]=true;
        p++;
        q--;
        
        if(p>=pre.size() || q<0){
            return root;
        }
        if(!vis[pre[p]]){
            
            int x=q;
            while(x>0 and pos[x]!=pre[p])x--;
            if(pos[x]==pre[p]){
                root->left=solve(pre,p,pos,x);
            }
            
        }
        if(!vis[pos[q]]){
            int x=p;
            while(x<pre.size()-1 and pos[q]!=pre[x])x++;
            if(pos[q]==pre[x]){
                root->right=solve(pre,x,pos,q);
            }
        }
        return root;
    }
        
    TreeNode* constructFromPrePost(vector<int>& preorder, vector<int>& postorder) {
        int n=postorder.size();
        return solve(preorder,0,postorder,n-1);
    }
};
var constructFromPrePost = function(preorder, postorder) {
    let preIndex = 0

    const dfs = (postArr) => {
        if (postArr.length === 0) return null

        const val = preorder[preIndex]
        const nextVal = preorder[++preIndex]
        const mid = postArr.indexOf(nextVal)

        const root = new TreeNode(val)
        root.left = dfs(postArr.slice(0, mid + 1))
        root.right = dfs(postArr.slice(mid + 1, postArr.indexOf(val)))

        return root
    }

    return dfs(postorder)
};
Construct Binary Tree from Preorder and Postorder Traversal