O(1). Concise. Fast. What's so hard?


  • 14

    This is definitely medium, not hard. Took me about 5 minutes, and some medium problems took me a few hours! Since you have to walk the tree in BFS order and you're given extra references to help you do just that, it's intuitive, it's simple and it's fast. The first level (root) is connected already, so you connect the next level and then you just walk through the linked list you've just created and so on.

    public void connect(TreeLinkNode root) {
        for (TreeLinkNode head = root; head != null; ) {
            TreeLinkNode nextHead = new TreeLinkNode(0), nextTail = nextHead;
            for (TreeLinkNode node = head; node != null; node = node.next) {
                if (node.left != null) {
                    nextTail.next = node.left;
                    nextTail = node.left;
                }
                if (node.right != null) {
                    nextTail.next = node.right;
                    nextTail = node.right;
                }
            }
            head = nextHead.next;
        }
    }

  • -3
    J

    O(logn)-------------------------------


  • 0

    Why? It's not recursive. Unless you count memory for pointers as O(log n), which kind of makes sense mathematically, but from practical standpoint it's traditionally considered O(1). In fact, both are true because log n <= 32 on 32-bit machines and <= 64 on 64-bit ones, hence O(log n) = O(32 or 64) = O(1).


  • 0
    C

    You don't need to allocate a node, the O(1) question becomes moot, and in C++ there is no memory leak.

    static void Append(TreeLinkNode** head, TreeLinkNode** tail, TreeLinkNode* node)
    {   if(!*tail)
            *head = node;
        else
            (*tail)->next = node;
        *tail = node;
    }
    static void connect(TreeLinkNode *root)
    {   for(TreeLinkNode* head = root; head != NULL;)
        {   TreeLinkNode* nextHead = NULL;
            TreeLinkNode* nextTail = NULL;
            for(TreeLinkNode* node = head; node != NULL; node = node->next)
            {   if(node->left)
                    Append(&nextHead, &nextTail, node->left);
                if(node->right)
                    Append(&nextHead, &nextTail, node->right);
            }
            head = nextHead;
        }
    }

  • 0

    It makes sense in C/C++, but in Java it will only lead to unnecessary branching since allocation is cheap.


  • 0

    The "node" pointer is not necessary, just use head to iterate through every parent level is fine.


  • 0

    True, but it will hardly affect performance (the compiler may optimize it away too), and I think it's a bit more readable this way (each variable is basically contained to its own loop).


  • 0

    BTW, also you can create the pseudo node just once at the very beginning then reuse it in the loop, just remember reset its next ptr to NULL every time.


  • 0

    That would make sense, yes. Especially when I can declare it in the for statement.


  • 0

    And that even makes it faster by 1 ms, by the way.


  • 0

    Actually, as mentioned in the comments above, it is possible to get the best of the two worlds in Java: allocate a sentinel, but only do it once and then reuse it. This makes the whole thing faster, makes life easier for the GC, and keeps the code as branch-free as possible.


Log in to reply
 

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