A non-recursive solution beat 100% by postorder travelsal.(C++)


  • -2
    F

    TreeNode* invertTree(TreeNode* root) {
    TreeNode* p = root;
    stack<TreeNode*> st;
    stack<bool> ft;

        while(p!=NULL||!st.empty()){
            while(p!=NULL){
                st.push(p);
                ft.push(true);
                p=p->left;
            }
            if(!st.empty()){
                p=st.top();
                bool f=ft.top();
                if(f){
                    ft.pop();
                    ft.push(false);
                    p=p->right;
                }else{
                    st.pop();
                    ft.pop();
                    TreeNode* tmp=p->left;
                    p->left=p->right;
                    p->right=tmp;
                    p=NULL;
                }
            }
        }//end while
        return root;
    }

Log in to reply
 

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