Straightforward Iterative solution with O(1) space


  • 0
    E

    Use two pointers: one is the current node we are working on; the other is current node's parent. When we are at current node, we should have already completed assigning parent's next pointers, so we can move parent to its next node very easily.

    Code in Java:

    public class Solution {
    public void connect(TreeLinkNode root) {
        if(root==null) return;
        TreeLinkNode parent = root; // current node's parent
        TreeLinkNode current = root.left; // current node we are working on
        TreeLinkNode next = root.right; // current node's next node
        TreeLinkNode firstNode = current; // first node of every level
        int leftOrRight = 1; // 1: current node is a left node; 2: current node is a right node.
        while(current != null) {
            if(leftOrRight==1) {
                next = parent.right;
                current.next = next;
                current = next;
                leftOrRight = 2; // current is now a right node
            }
            else {
                if(parent.next != null) { // parent's next pointer is not null, thus moves to parent's next node
                    parent = parent.next;
                    next = parent.left;
                    current.next = next;
                    current = next;
                }
                else { // parent's next pointer is null, thus moves to next level
                    current.next = null;
                    parent = firstNode;
                    current = parent.left; // current moves to next level
                    firstNode = current; // first node of next level
                }
                leftOrRight = 1; // current is now a left node
            }
        }
    }
    }

Log in to reply
 

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