Concise C++ O(n) solution


  • 0
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            vector<TreeNode*> parent;
            TreeNode *prev = nullptr;
            int i = 0, j = 0, n = inorder.size();
            while(j < n) {
                while(!parent.empty() && postorder[j] == parent.back() -> val) {
                    parent.back() -> right = prev;
                    prev = parent.back();
                    parent.pop_back();
                    j++;
                }
                if(i < n) {
                    parent.push_back(new TreeNode(inorder[i++]));
                    parent.back() -> left = prev;
                    prev = nullptr;
                }
            }
            return prev;
        }
    

Log in to reply
 

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