8ms, Non-recursive, No stack, C++ solution


  • 48
    J
    void flatten(TreeNode *root) {
    	while (root) {
    		if (root->left && root->right) {
    			TreeNode* t = root->left;
    			while (t->right)
    				t = t->right;
    			t->right = root->right;
    		}
    
            if(root->left)
    		    root->right = root->left;
    		root->left = NULL;
    		root = root->right;
    	}
    }

  • 0

    A bit different though but my code ended up almost the same as yours :)

    var flatten = function(root) {
        while (root) {
            if (root.left) {
                var t = root.left;
                while (t.right) {
                    t = t.right;
                }
                t.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    };
    

    And later I found out your solutions is better, and tweak it a bit as the following. There's no need to set left to null if it's already null. But anyway, this wont improve too much :)

    var flatten = function(root) {
        while (root) {
            if (root.left && root.right) {
                var t = root.left;
                while (t.right) {
                    t = t.right;
                }
                t.right = root.right;
            }
    
            if (root.left) {
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    };
    

  • 0

    Excuse me, but what is the time complexity of this algorithm? Thanks.


  • 0
    J

    The time complexity is O(n). We visit every single node only one time.


  • 3
    X

    When flattening every TreeNode, it will go down to find the last element of left subtree. So I think it is O(nlogn).


  • 0
    F

    @xiesheng I think each node will be visited at most two times, so the run time should be O(n)


  • 1
    L

    @for_the_glory As @xiesheng said, every step, you need to find left subtree's deepest right element. Many nodes will be visited much more than 2 times.


  • 0
    H

    Awesome and beautiful!


  • 0
    E

    3ms

    class Solution {
    private:
        TreeNode* flattenAux(TreeNode* root) {
            if(!root) return NULL;
            TreeNode *l = root->left, *r = root->right, *tmp = root;
            root->left = NULL;
            if(l) {
                tmp = flattenAux(l);
                root->right = l;
                root = tmp;
            }
            if(r) {
                tmp = flattenAux(r);
                root->right = r;
            }
            return tmp;
        }
    public:
        void flatten(TreeNode* root) {
            flattenAux(root);
        }
    };
    

Log in to reply
 

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