binary tree from inorder and postorder.txt

Binary Tree From Inorder And Postorder
Problem Description

Given inorder and postorder traversal of a tree, construct the binary tree.

NOTE: You may assume that duplicates do not exist in the tree.



Problem Constraints
1 <= number of nodes <= 105



Input Format
First argument is an integer array A denoting the inorder traversal of the tree.

Second argument is an integer array B denoting the postorder traversal of the tree.



Output Format
Return the root node of the binary tree.



Example Input
Input 1:

 A = [2, 1, 3]
 B = [2, 3, 1]
Input 2:

 A = [6, 1, 3, 2]
 B = [6, 3, 2, 1]


Example Output
Output 1:

   1
  / \
 2   3
Output 2:

   1  
  / \
 6   2
    /
   3


Example Explanation
Explanation 1:

 Create the binary tree and return the root node of the tree.


/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 map<int,int> mp;
 TreeNode* solve(vector<int> &A,vector<int> &B,int inStart,int inEnd,int pStart,int pEnd){
     if(inStart>inEnd or pStart>pEnd){
         return NULL;
     }
     TreeNode *temp=new TreeNode(B[pEnd]);
     int index=(*mp.find(B[pEnd])).second;
     int n=index-inStart;
     temp->left=solve(A,B,inStart,index-1,pStart,pStart+n-1);
     temp->right=solve(A,B,index+1,inEnd,pStart+n,pEnd-1);
     return temp;
     
 }
TreeNode* Solution::buildTree(vector<int> &A, vector<int> &B) {
    mp.clear();
    for(int i=0;i<A.size();i++){
        mp[A[i]]=i;
    }
    int n=A.size();
    return solve(A,B,0,n-1,0,n-1);
}