12ms C++ solution O(n) space and time


  • 3
    T
    /**
     * 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) {
            int size = inorder.size();
            
            TreeNode** path = (TreeNode**)malloc(sizeof(TreeNode*)*(size + 1));
            TreeNode* dummy = new TreeNode(0xDEADBEEF);
            path[0] = dummy;
            TreeNode* root = dummy;
            
            int pathIdx = 0;
            int inIdx = size - 1;
            int postIdx = size - 1;
            
            while(postIdx >= 0){
                if(path[pathIdx]->val == inorder[inIdx]){
                    root = path[pathIdx];
                    pathIdx--;
                    inIdx--;
                }
                else{
                    TreeNode* head= new TreeNode(0);
                    TreeNode* node = head;
                    
                    while(postorder[postIdx] != inorder[inIdx]){
                        node->right = new TreeNode(postorder[postIdx]);
                        postIdx--;
                        node = node->right;
                        path[++pathIdx] = node;
                    }
                    
                    node->right = new TreeNode(postorder[postIdx]);
                    node = node->right;
                    path[++pathIdx] = node;
                    postIdx--;
                    root->left = head->right;
                    delete head;
                }
            }
            
            return dummy->left;
        }
    };

  • 0

    How do you find this?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.