A simple solution through preorder traversal in O(n).


  • 0
    R

    stack<TreeNode*> s;
    void func(TreeNode* root)
    {
    TreeNode* temp;
    
    if(root==NULL)
        return ;
    
    if(root->left==NULL)
    {   if(root->right==NULL)
        while(!s.empty())
        {
            temp=s.top();
            s.pop();
           
          if(root->right!=NULL)
               s.push(root->right);
           
            root->right=temp;
            func(temp);
        }
        func(root->right);
        return ;
    }
    else
    {
        s.push(root->right);
        root->right=root->left;
        root->left=NULL;
        func(root->right);
    }
    

    }

    class Solution {
    public:
    void flatten(TreeNode* root) {
         func(root);   
    }
    

    };


Log in to reply
 

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