C++ DFS binary tree search - non-recursive solution


  • 0
    H

    my code is

    class Solution {
    public:
        vector<string> generateParenthesis(int n) {
            if(!n) return vector<string>();
           string st; st.reserve(n+1);
            vector<string>  results;
            int open = 0, close = 0;
            st.push_back('('); ++open;
            while(st.size()){
                ///DFS for binary tree
                //// '(' left, ')' right; 
                if(open < n){  ////visit the left child 
                    st.push_back('(');
                    ++open;
                }else if(close < n){ ///visit the right child
                    st.push_back(')');
                    ++close;
                }else{
                    results.push_back(st);
                     while( st.size()){
                        char c = st.back();
                        st.pop_back();
                        if( c == ')'){
                            --close;
                        }else{
                            --open;
                            
                            if(open > close){ ///consistency condition: open >= close
                                st.push_back(')');
                                ++close;
                                break;
                            }
                        }
                    }
                }
            }
            return results;
        }
    };
    

Log in to reply
 

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