Given a binary tree:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: The given binary tree is shown in Figure A. Your function should populate each next pointer to point to its next right node, as shown in Figure B. The serialized output follows the level order traversal (connected by next pointers), with # indicating the end of each level.

Example 2:

Input: root = []
Output: []

Solution 1 BFS

Copy the code from problem 116 directly, no changes needed.

Use a queue to store the nodes of the next level. Use the pre pointer to link the elements in the queue one by one.

public Node connect(Node root) {
    if (root == null) {
        return root;
    }
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        Node pre = null;
        for (int i = 0; i < size; i++) {
            Node cur = queue.poll();
            if (i > 0) {
                pre.next = cur;
            }
            pre = cur;
            if (cur.left != null) {
                queue.offer(cur.left);
            }
            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }
    return root;
}

Solution 2

Refer to problem 116 for the idea. Modify it slightly here.

Node connect(Node root) {
    if (root == null)
        return root;
    Node pre = root;
    Node cur = null;
    while (pre.left != null) {
        cur = pre;
        while (cur != null) {
            cur.left.next = cur.right;
            if (cur.next != null) {
                cur.right.next = cur.next.left;
            }
            cur = cur.next;
        }
        pre = pre.left;
    }
    return root;
}

The key lines are:

cur.left.next = cur.right;
cur.right.next = cur.next.left;

How ever, in this problem, we cannot guarantee that cur.left, cur.right, cur.next.left, or cur.next.right is not null. So we use a while loop to ensure the current node has at least one child.

while (cur.left == null && cur.right == null) {
    cur = cur.next;
}

This ensures the current node has atleast one child. If one child is null, the other must not be null.

The overall approach uses the above technique, and the code is longer. You can review it in combination with the explanation.

Node connect(Node root) {
    if (root == null)
        return root;
    Node pre = root;
    Node cur = null;
    while (true) {
        cur = pre;
        while (cur != null) {
            // find a node with at least one child
            if (cur.left == null && cur.right == null) {
                cur = cur.next;
                continue;
            }
            // find the next node with at least one child
            Node next = cur.next;
            while (next != null && next.left == null && next.right == null) {
                next = next.next;
                if (next == null) {
                    break;
                }
            }
            // connect left and right
            if (cur.left != null && cur.right != null) {
                cur.left.next = cur.right;
            }
            // handle cases where right is null
            Node temp = cur.right == null ? cur.left : cur.right;
            if (next != null) {
                if (next.left != null) {
                    temp.next = next.left;
                } else {
                    temp.next = next.right;
                }
            }
            cur = cur.next;
        }
        // find the first node with children
        while (pre.left == null && pre.right == null) {
            pre = pre.next;
            if (pre == null) {
                return root;
            }
        }
        // move to the next level
        pre = pre.left != null ? pre.left : pre.right;
    }
}

Solution 3

Reference: https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/solutions/138393/concise-fast-what-s-so-hard/

Use the idea from solution 1. Use the pre pointer to traverse and link nodes. Why didn't solution 1 consider the case where the current node is null? Because we don't add null nodes to the queue, which is handled by the following code:

if (cur.left != null) {
    queue.offer(cur.left);
}
if (cur.right != null) {
    queue.offer(cur.right);
}

So, if the current node is null, we skip it.

The second issue is how to get the starting node of each level. We use a dummy pointer. When connecting the first node, we set the dummy pointer to it. Using the pre pointer as a tail pointer may be easier to understand. As shown in the diagram:

The cur pointer traverses the current level using next.

If the current node's children are not null, they are added to the tail. Then the tail pointer is updated.

When cur is null, we use the dummy pointer to get the start of the next level.

The dummy pointer is often used in linked lists to handle the head node, but it does not belong to the current list.

The code becomes very simple.

Node connect(Node root) {
    Node cur = root;
    while (cur != null) {
        Node dummy = new Node();
        Node tail = dummy;
        while (cur != null) {
            if (cur.left != null) {
                tail.next = cur.left;
                tail = tail.next;
            }
            if (cur.right != null) {
                tail.next = cur.right;
                tail = tail.next;
            }
            cur = cur.next;
        }
        cur = dummy.next;
    }
    return root;
}