24ms C++ solution using o(1) space


  • 1
    X

    It is very easy to come up with a solution using recursion. But the space cost of a recursion solution is o(lgn), but not o(1). Here is my c++ solution using o(1) extra space,

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if ( root == NULL ) return;
            TreeLinkNode* node = root;
            while (node->left) { 
                node->left->next = node;
                node = node->left;
            }
    
            while (node != root) {
                if (node == node->next->left) {
                    node->next->right->next = node->next;
                    node->next = node->next->right;
                    while (node->right) {
                        node->next->left->next = node->next;
                        node->right->next = node->next->left;
                        node = node->right;
                    }
                    node = node->next;
                } 
                else if (node == node->next->right) {
                    while ( node != root && node == node->next->right) {
    
                        node = node->next;
                        node->right->next = NULL;
                    }
                }
            }
    
        }
    };

  • 0
    S

    Thanks @ xie.jun !! Great solution !!!


Log in to reply
 

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