O(n) Java solution, very easy to understand


  • 5
    J
    public void connect(TreeLinkNode root) {
        if(root == null) return;
        TreeLinkNode le = root.left;
        TreeLinkNode ri = root.right;
        while(le != null) {
            le.next = ri;
            le = le.right;
            ri = ri.left;
        }
        connect(root.left);
        connect(root.right);
    }
    

    Every root only takes care of connecting the rightmost nodes in its left child to the leftmost nodes in its right child. Then recurse.


  • 0
    S

    This algo is wrong:

         1 -> NULL
       /  \
      2 -> 3 -> NULL
     / \  / \
    4->5->6->7 -> NULL
    

    you will not get 5 -> 6 for example


  • 0
    J

    It will because the while loop goes all the way down to the leaf. Run it on your own machine if you don't believe me :)


  • 0
    H

    I believe Joshua is correct. The algo actually did all connecting work between two trees by the last two lines in the loop.
    Pretty smart work, Joshua.


Log in to reply
 

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