106. Construct Binary Tree from Inorder and Postorder Traversal

秒速五厘米 2022-05-12 15:16 184阅读 0赞

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

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

For example, given

inorder = [9,3,15,20,7]
    postorder = [9,15,7,20,3]

Return the following binary tree:

3
       / \
      9  20
        /  \
       15   7

/**
     * 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 {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
        {
            if(postorder.size() == 0 || inorder.size() == 0)
              return NULL;
                  
            int value = postorder[postorder.size()-1];
            TreeNode* root = new  TreeNode(value);
    
            vector<int> inorderL;
            vector<int> inorderR;
            bool flag = true;
            int index = 0;
            for(int i = 0; i < inorder.size(); i++)
            {
                if(inorder[i] == value)
                {
                    flag = false;
                    index = i;
                }              
                if(flag)
                    inorderL.push_back(inorder[i]);
                else if(i>index)
                    inorderR.push_back(inorder[i]);
            }
    
            vector<int> postorderL;
            vector<int> postorderR;
            for(int j = 0; j < postorder.size()-1; j++)
            {
                if(j<index)
                    postorderL.push_back(postorder[j]);
                else  
                    postorderR.push_back(postorder[j]);
            }
    
            root->left = buildTree(inorderL, postorderL);
            root->right = buildTree(inorderR, postorderR);
            return root;
        }
    };