Fast C++ solutions (recursive and iterative)


  • 0
    G

    Recursive solution with hashmap

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            unordered_map<int, int> map;
            for (int i = 0; i < inorder.size(); ++i)
            {
                map[inorder[i]] = i;
            }
            
            return helper(0, postorder.size() - 1, 0, inorder.size() - 1, postorder, map);
        }
        
        TreeNode* helper(int poStart, int poEnd, int inStart, int inEnd, vector<int>& postorder, unordered_map<int, int>& map)
        {
            if (poStart > poEnd || inStart > inEnd)
            {
                return NULL;
            }
            
            int mid = postorder[poEnd];
            TreeNode* root = new TreeNode(mid);
            int inIndex = map[mid];
            
            root->left = helper(poStart, poStart + inIndex - inStart - 1, inStart, inIndex - 1, postorder, map);
            root->right = helper(poStart + inIndex - inStart, poEnd - 1, inIndex + 1, inEnd, postorder, map);
            
            return root;
        }
        
    };
    

    Iterative solution with stack

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            if (inorder.empty())
            {
                return NULL;
            }
            
            TreeNode *dummy = new TreeNode(0x80000000);
            stack<TreeNode*> nodeStack;
            nodeStack.push(dummy);
            TreeNode *prev = NULL, *curr = dummy;
            int in = inorder.size() - 1, po = postorder.size() - 1;
            
            while (in >= 0)
            {
                if (nodeStack.top()->val == inorder[in])
                {
                    prev = nodeStack.top();
                    nodeStack.pop();
                    --in;
                }
                else if (prev)
                {
                    curr = new TreeNode(postorder[po]);
                    prev->left = curr;
                    nodeStack.push(curr);
                    prev = NULL;
                    --po;
                }
                else
                {
                    curr = new TreeNode(postorder[po]);
                    nodeStack.top()->right = curr;
                    nodeStack.push(curr);
                    --po;
                }
            }
            
            curr = dummy->right;
            delete dummy;
            
            return curr;
        }
    };

Log in to reply
 

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