116. Populating Next Right Pointers in Each Node

, ,

BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        if (root != null) {
            queue.offer(root);
        }

        while (!queue.isEmpty()) {
            Node pre = null;
            for (int i = queue.size(); i > 0; i--) {
                Node node = queue.poll();
                node.next = pre;
                pre = node;
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
        }

        return root;
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Node leftmost = root;
        while (leftmost.left != null) {
            // 存在下层节点

            Node node = leftmost;
            while (node != null) {
                // 处理该层所有节点
                node.left.next = node.right;
                if (node.next != null) { // 最右侧节点的 next 为空
                    node.right.next = node.next.left;
                }

                node = node.next;
            }

            leftmost = leftmost.left;
        }

        return root;
    }
}

Iterate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public Node connect(Node root) {
        Node leftmost = root;
        while (leftmost != null) {
            Node nextLayerDummyHead = new Node(); // 下一层的哑节点
            Node pre = nextLayerDummyHead, curr = leftmost;
            while (curr != null) { // 遍历当前层节点，并连接下一层节点
                if (curr.left != null) {
                    pre.next = curr.left;
                    pre = pre.next;
                }
                if (curr.right != null) {
                    pre.next = curr.right;
                    pre = pre.next;
                }

                curr = curr.next;
            }

            leftmost = nextLayerDummyHead.next; // 进入下一层
        }

        return root;
    }
}

Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        connect(root.left, root.right);

        return root;
    }

    private void connect(Node nodeA, Node nodeB) {
        if (nodeA == null || nodeB == null) {
            return;
        }

        nodeA.next = nodeB;

        connect(nodeA.left, nodeA.right);
        connect(nodeB.left, nodeB.right);
        connect(nodeA.right, nodeB.left);
    }
}

References

116. Populating Next Right Pointers in Each Node