C++ one stack & one queue


  • 0
    Y

    recursive version is fancy, but I'd like to know exactly what is going on, so came up with this stack queue solution.

    Stack is used for Preorder traversal, queue stores the order.
    At the end, iterate through the queue, relink each node to its next neighbor.

    class Solution {
    public:
        void flatten(TreeNode* root) {
            if(!root)
                return;
            vector<TreeNode*> ss;
            vector<TreeNode*> seq;
            TreeNode* cur =root;
            while(cur || ss.size() ){
                if(cur){
                    ss.push_back(cur);
                    seq.push_back(cur);
                    cur=cur->left;
                }else{
                    cur =ss.back();
                    ss.pop_back();
                    cur=cur->right;
                }
            }
            int size = seq.size();
            for(int i=0; i< size ; i++){
                seq[i]->left =NULL;
                if(i<size-1)
                    seq[i]->right =seq[i+1];
                else
                    seq[i]->right=NULL;
            }
        }
    };
    

Log in to reply
 

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