Java solution with constant space


  • 113
    A
    public void connect(TreeLinkNode root) {
        TreeLinkNode dummyHead = new TreeLinkNode(0);
        TreeLinkNode pre = dummyHead;
        while (root != null) {
    	    if (root.left != null) {
    		    pre.next = root.left;
    		    pre = pre.next;
    	    }
    	    if (root.right != null) {
    		    pre.next = root.right;
    		    pre = pre.next;
    	    }
    	    root = root.next;
    	    if (root == null) {
    		    pre = dummyHead;
    		    root = dummyHead.next;
    		    dummyHead.next = null;
    	    }
        }
    }

  • 2
    S

    This answer is brilliant! It is a real O(1) solution!


  • 0
    C

    Totally agree. Brilliant thought .:)


  • 0

    come on man, your solution is nice!


  • 0
    Y

    The dummyHead idea is awesome, saved a lot of check.


  • 0
    P

    Thanks for sharing ! Can I ask that what is the meaning of the code "pre = dummyHead; " ?
    Can anyone answer me?


  • 0
    R

    Very nice solution! Thanks a lot!


  • 0
    K

    Excellent easy to understand solution!


  • 0
    T

    @airwindow Beautiful solution! Very skillful use of dummyHead!


  • 1
    T

    @PeterP I didn't write the code, but from my understanding, the point of that is to move pre back to dummyHead in order to get ready for the next level (or not if there is no more level). Basically you move pre back to dummyHead and you move root to dummyHead.next (which is the left most of the current level), so that when you go back to the beginning of the while loop, pre will go to the most left node of the next level (root.left).


  • 0
    X

    I don't understand that why the following code can change the level
    if (root == null) {
    pre = dummyHead;
    root = dummyHead.next;
    dummyHead.next = null;
    }


  • 0
    S

    @xysrGeeemm If you draw the execution process step by step, you will get the idea. That was what I did to figure it out.


  • 0

    @xysrGeeemm Hi did you understand? I'm not able to either


  • 0
    F

    @xysrGeeemm
    dummyHead always points to a dummyNode, and pre is just a pointer.
    dummyHead links all the node of one level.
    When root is null, we need to shift to next level, so dummyNode.next points to the first avaible node on next level.
    Also we need to reset pre


  • 0
    V

    the dummyHead is very smart, brilliant.


  • 0
    S

    Hi thanks for this beautiful solution! Though I can't believe I spent quite amount of time understanding the relationship between dummyHead and prev. Finally I got it by going through the process step by step.

    Still has a minor question though: why we need "dummyHead.next = null;" at the end? Since in the next loop, pre (which also points at dummyHead at first).next would be set to either root.left or root.right, why do we need to set dummyHead.next = null before that?

    I tried to eliminate this line but got a TLE. Still have some doubts on it. Any help would be appreciated!


  • 0
    B

    @Sparrow_M
    when root == null, it means that this is the last node in this layer. Currently you can think dummyHead is a head of a LinkedList, dummyHead.next is the starting node of next layer.

    So, when we come to the last node, we need to shift to next layer, that's why we need to have root = dummyHead.next.
    we need to reset our helper pointer pre to dummyHead. And finally, cut off all the previous node because it does not belong to this layer.


Log in to reply
 

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