16 ms c++ iterative solution


  • 0
    H

    Iterative version with reference to https://discuss.leetcode.com/topic/10244/my-o-n-19ms-solution-without-recusion-hope-help-you

    class Solution {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
            TreeNode* root = nullptr;
            int m = inorder.size();
            int n = postorder.size();
            if (m == 0 || n == 0) return root;
            int j = m - 1;
            stack<TreeNode*> s;
            root = new TreeNode(postorder[n-1]);
            s.push(root);
            for (int i = n-2; i >= 0; i--) {
                TreeNode* cur = s.top();
                if (cur->val == inorder[j]) {
                    while(!s.empty() && s.top()->val == inorder[j]) {
                        cur = s.top();
                        s.pop();
                        j--;
                    }
                    if (j >= 0) {
                        if (!s.empty() && inorder[j] == postorder[i]) {
                            cur->left = new TreeNode(inorder[j]);
                        }
                        else {
                            cur->left = new TreeNode(postorder[i]);
                        }
                        s.push(cur->left);
                    }
                }
                else {
                    cur->right = new TreeNode(postorder[i]);
                    s.push(cur->right);
                }
            }
            return root;
        }
    };
    

Log in to reply
 

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