106. Construct Binary Tree from Inorder and Postorder Traversal

 106Construct Binary Tree from Inorder and Postorder Traversal


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.

 

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]

 

Constraints:

  • 1 <= inorder.length <= 3000
  • postorder.length == inorder.length
  • -3000 <= inorder[i], postorder[i] <= 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.

The solution to the above question


/**
 * 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:
    TreeNode* helper(vector<int>&invector<int>& postint insint ineint posint poe){
        if(ins>ine){
            return NULL;
        }
        int idx=0;
        for(int i=insi<=inei++){
            if(in[i]==post[poe]){
                idx=i;
                break;
            }
        }
        int inls=ins;
        int inrs=idx+1;
        int inle=idx-1;
        int inre=ine;
        int pls=pos;
        int pre=poe-1;
        int ple=pls+inle-inls;
        int prs=ple+1;
        
        
        
        TreeNode* root=new TreeNode(post[poe]);
        root->left=helper(in,postinlsinleplsple);
        root->right=helper(inpostinrsinreprspre);
        
            return root;
        
    }
    
    TreeNode* buildTree(vector<int>& inordervector<int>& postorder) {
        return helper(inorder,postorder,0,inorder.size()-1,0,postorder.size()-1);
    }
};

Post a Comment

0 Comments