Java O(1) space solution using one dummy node. Very easy to understand.


  • 0
    Z

    All we need is a dummy node, which will be repeatedly used as the head to chain through each level.

        public void connect(TreeLinkNode root) {
            TreeLinkNode dummy = new TreeLinkNode(0);  ///* dummy node, used as head for chaining each level *
            TreeLinkNode prev = root, curr = dummy; // two pointers: used for traversal through each level
            
            while (prev != null) {
                while (prev != null) {
                    if (prev.left != null) {
                        curr.next = prev.left;
                        curr = curr.next;
                    }
                    if (prev.right != null) {
                        curr.next = prev.right;
                        curr = curr.next;
                    }
                    prev = prev.next;
                }
                prev = dummy.next;  // move to next level, which starts as dummy.next
                dummy.next = null; // cut out the dummy node 
                curr = dummy;  // curr pointer ready for chaining next level
            }
        }

Log in to reply
 

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