116. Populating Next Right Pointers in Each Node

Problem

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Example 2:

Input: root = []
Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 212 - 1].
• -1000 <= Node.val <= 1000

Solution

此題要我們將每一層中的左邊 node 的 next 指向右邊的 node。因為是一層一層地處理，所以很直覺地可以想到用 BFS 來解。我們需要兩個 queue，這樣才可以分清目前的層與下一層。因為題目有提到是 perfect binary tree，所以每個 node 的 left child 可以直接指向 right child。在將 left child 加到 queue 之前，將 queue 裡最後一個 node 指向 left child。

BFS

• Time:
• Space:

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Deque<Node> currentLevel = new ArrayDeque<>();
        Deque<Node> nextLevel = new ArrayDeque<>();
        currentLevel.offer(root);
        
        while (!currentLevel.isEmpty()) {
            Node node = currentLevel.poll();
            if (node.left != null) {
                if (!nextLevel.isEmpty()) {
                    nextLevel.peekLast().next = node.left;
                }
                nextLevel.offer(node.left);
                node.left.next = node.right;
                nextLevel.offer(node.right);
            }

            if (currentLevel.isEmpty()) {
                currentLevel = nextLevel;
                nextLevel = new ArrayDeque<>();
            }
        }
        return root;
    }
}

參考

• 116. Populating Next Right Pointers in Each Node, LeetCode.
• 116. Populating Next Right Pointers in Each Node, LeetCode Solutions.