C++ 12ms iterative solution


  • 0
    X
       TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
            if(preorder.empty()){
                return NULL;
            }
            TreeNode* root = new TreeNode(preorder[0]);
            TreeNode* pre = root;
            stack<TreeNode*> st;
            st.push(root);
            int flag = 0;
            int pp = 1, pi = 0;
            while(pi < inorder.size()){
                if(!st.empty() && st.top()->val == inorder[pi]){
                    pre = st.top();
                    flag = 1;
                    st.pop();
                    ++pi;
                }else{
                    TreeNode* tmp = new TreeNode(preorder[pp]);
                    if(flag == 0){
                        pre->left = tmp;
                        pre = pre->left;
                    }else{
                        pre->right = tmp;
                        pre = pre->right;
                        flag = 0;
                    }
                    st.push(tmp);
                    ++pp;
                }
            }
            return  root;
        }

Log in to reply
 

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