11 lines C++ DFS


  • 0
    class Solution {
    public:
        void flatten(TreeNode* root) {
            TreeNode* l, *r;
            DFS(root, l, r);
        }
        
        TreeNode* DFS(TreeNode* &root, TreeNode* &l, TreeNode* &r){
            if(!root) return NULL;
            l = DFS(root->left, l, r);
            if(l){
                l->right = root->right;
                root->right = root->left;
                root->left = NULL;
            }
            r = DFS(root->right, l, r);
            return r ? r : l ? l : root;
        }
    };
    

    O(1) space iterative.

    class Solution {
    public:
        void flatten(TreeNode* root) {
            TreeNode* p;
            while(root){
                if(root->left && root->right){
                    p = root->left;
                    while(p->right) p = p->right;
                    p->right = root->right;
                }
                if(root->left) root->right = root->left;
                root->left = NULL;
                root = root->right;
            }
        }
    };
    

  • 0
    F

    This is not o(1) space... you are using recursion?


  • 0

    @felder You are right, thanks for pointing out, I have changed the solution to & (reference), now it's O(1) space.


  • 0
    F

    @zefengsong although that removes some of the things on the stack, the stack still increases each recursive call to keep track of where to return too as well as other holder variables. So although you do reduce by passing by reference, recursive solution is still not o(1) in space. it is O(how many nodes there are)


  • 0

    @felder I see, context switch between each recursive call can cost extra space. THX, i need to change my title then :)


  • 0

    @felder I have added iterative version.


Log in to reply
 

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