C++ O(n) Time / O(logn) Space Recursive Solution: Beats 98% submission


  • 0
    E

    Core Idea:

    When you reverse the postorder, it has 'root->right->left' order, which is very similar to preorder. Then you want to revert inorder as well to have 'right->root->left' order. Now you can think it as same problem with "Construct Tree Using Preorder and Inorder", only changing left tree to right tree.

    /**
     * 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 (inorder.empty() || inorder.size() != postorder.size())
                return nullptr;
            
            // now post order becomes preorder like: root->right->left
            reverse(postorder.begin(), postorder.end());
            // inorder is still inorder but start from right: right->root->left
            reverse(inorder.begin(), inorder.end());
            stack<TreeNode*> st;
            TreeNode* node = new TreeNode(postorder[0]);
            TreeNode* root = node;
            int poIdx = 1;
            int inIdx = 0;
            for (; poIdx < postorder.size(); ++poIdx) {
                TreeNode* newNode = new TreeNode(postorder[poIdx]);
                if (inorder[inIdx] != node->val) {
                    node->right = newNode;
                    st.push(node);
                    node = newNode;
                } else {
                    ++inIdx;
                    while (!st.empty() && inorder[inIdx] == st.top()->val) {
                        ++inIdx;
                        node = st.top();
                        st.pop();
                    }
                    
                    node->left = newNode;
                    node = newNode;
                }
            }
            
            return root;
        }
    };
    

Log in to reply
 

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