117. Populating Next Right Pointers in Each Node II

Problem

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: Given the above 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, 6000].
• -100 <= Node.val <= 100

Solution

此題要我們將每一層中的左邊 node 的 next 指向右邊的 node。因為是一層一層地處理，所以很直覺地可以想到用 BFS 來解。我們需要兩個 queue，這樣才可以分清目前的層與下一層。在將 每個 child 加到 queue 之前，將 queue 裡最後一個 node 指向 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);
            }
            if (node.right != null) {
                if (!nextLevel.isEmpty()) {
                    nextLevel.peekLast().next = node.right;
                }
                nextLevel.offer(node.right);
            }

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

參考

• 117. Populating Next Right Pointers in Each Node II, LeetCode.
• 117. Populating Next Right Pointers in Each Node II, LeetCode Solution.