16 ms O(n) c++ solution using stack


  • 0
    Z

    Based on Construct Binary Tree from Preorder and Inorder Traversal

     class Solution {
        public:
            TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
                stack<TreeNode*> st;
                TreeNode* root=NULL;
                if(!preorder.size())return root;
                root=new TreeNode(preorder[0]);
                st.push(root);
                int j=0;
                for(int i=1;i<preorder.size();i++){
                    TreeNode *cur=st.top();
                    if(cur->val!=inorder[j]){
                        cur->left=new TreeNode(preorder[i]);
                        st.push(cur->left);
                    }
                    else{
                        while(!st.empty()&&st.top()->val==inorder[j]){
                            j++;cur=st.top();st.pop();
                        }
                        if(j<preorder.size()){
                            cur->right=new TreeNode(preorder[i]);
                            st.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.