Share my 12ms c++ non-recursive solution (beats 97%)


  • 0
    L
    class Solution {
    public:
        TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            
            if (preorder.empty()) return NULL;
    
            int pcur(0),icur(0);
            stack<TreeNode*> st;
            TreeNode* root = NULL;
            TreeNode** cur = &root;
            
            while (pcur<preorder.size()){
                TreeNode* temp = new TreeNode(preorder[pcur]);
                *cur = temp;
                
                if (preorder[pcur]!=inorder[icur]){
                    st.push(temp);
                    cur = &temp->left;
                }
                else{
                    cur = &temp->right;
                    icur++;
                    while(icur<inorder.size() && !st.empty() && inorder[icur]==st.top()->val){
                        cur = &(st.top()->right);
                        st.pop();
                        icur++;
                    }
                }
                pcur++;
            }
            return root;
        }
    };

Log in to reply
 

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