[117. Populating Next Right Pointers in Each Node II] #leetcode

117_0829.java

public class Solution {
  // O(n) O(n)
    public void connect(TreeLinkNode root) {
        if ( root == null ) return;
        
        Deque<TreeLinkNode> deque = new LinkedList<TreeLinkNode>();
        deque.addLast(root);
        
        while ( !deque.isEmpty() ) {
            int n = deque.size();
            for ( int i = 0 ; i < n ; i++ ) {
                TreeLinkNode node = deque.removeFirst();
                if ( i != n - 1 ) {
                    node.next = deque.peekFirst();
                }
                if ( node.left != null ) deque.addLast(node.left);
                if ( node.right != null ) deque.addLast(node.right);
            }
        }
    }
}

public class Solution {
  // O(n) O(1) 
    public void connect(TreeLinkNode root) {
        while ( root != null ) {
            TreeLinkNode leftmostChild = new TreeLinkNode(0);
            TreeLinkNode currentChild = leftmostChild;
            while ( root != null ) {
                if ( root.left != null ) {
                    currentChild.next = root.left;
                    currentChild = currentChild.next;
                }
                if ( root.right != null ) {
                    currentChild.next = root.right;
                    currentChild = currentChild.next;
                }
                root = root.next;
            }
            root = leftmostChild.next;
        }
    }
}