Share my 20 line NON-recursive solution


  • 1
    W

    Using a stack to do pre-order traverse and build up the result while treversing:

    void flatten(TreeNode *root) {
        if(root == NULL)
            return;
        stack<TreeNode*> sk;
        TreeNode* tail = NULL;
        sk.push(root);
        
        while(!sk.empty()){
            TreeNode * cur = sk.top();
            sk.pop();
            if(cur->right != NULL)
                sk.push(cur->right);
            if(cur->left != NULL)
                sk.push(cur->left);
            
            if(tail != NULL){
                tail->right = cur;
                tail->left = NULL;
            }
            tail = cur;
        }
        return;
    }

  • 0
    K

    Yep, the hint of this problem mentions that the node's right pointers points to the next node of a pre-order traversal.


  • 0
    S

    cool, and I think using a stack is essentially the same as using a recursive function, maybe faster?


  • 0
    L

    Simple code with a driver function

    vector <TreeNode* > v;
         void func(TreeNode *root)
         {
           if(root)
           {
               v.push_back(root);
               func(root->left);
               func(root->right);
           }
      
         }
    
        void flatten(TreeNode *root) {
            if(root==NULL)
             return;
             
            func(root);
            
            for(int i=1 ; i<v.size() ; i++)
            { 
              root->left=NULL;
              root->right=v[i];
              root=root->right;
            }
        }

  • 0
    F

    I think the problem want a IN PLACE solution


  • 0
    W

    You are right ! Here is IN PLACE solution: (which needs only O(1) space)

    void flatten(TreeNode *root) {
        if(!root)
            return;
        while(root){
            if(root->left){
                if(root->right){
                    TreeNode* rc = root->left;
                    while(rc->right){
                        rc = rc->right;
                    }
                    rc->right = root->right;
                }
                root->right = root->left;
                root->left = NULL;
            }
            root = root->right;
        }
    }

  • 0
    W

    Yes the are essentially same but stack should be faster , since we avoid stuff like. function call stack pop , moving sp pointer ...


Log in to reply
 

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