116. Populating Next Right Pointers in Each Node

public class Solution {
    public Node Connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> Q = new Queue<Node>();
        Q.Enqueue(root);
        while (Q.Count > 0) {
            int size = Q.Count;
            for (int i = 0; i < size; i++) {
                Node node = Q.Dequeue();
                if (i < size - 1) {
                    node.next = Q.Peek();
                }
                if (node.left != null) {
                    Q.Enqueue(node.left);
                }
                if (node.right != null) {
                    Q.Enqueue(node.right);
                }
            }
        }
        return root;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public Node Connect(Node root) {
        if (root == null) {
            return root;
        }
        queue<Node> Q = new queue<Node>();
        Q.Enqueue(root);
        while (Q.size() > 0) {
            int size = Q.size();
            for (int i = 0; i < size; i++) {
                Node node = Q.Dequeue();
                if (i < size - 1) {
                    node.next = Q.Peek();
                }
                if (node.left != null) {
                    Q.Enqueue(node.left);
                }
                if (node.right != null) {
                    Q.Enqueue(node.right);
                }
            }
        }
        return root;
    }
}

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }

        Queue<Node> Q = new LinkedList<Node>();
        Q.add(root);

        while (Q.size() > 0) {
            int size = Q.size();

            for (int i = 0; i < size; i++) {
                Node node = Q.poll();

                if (i < size - 1) {
                    node.next = Q.peek();
                }

                if (node.left != null) {
                    Q.add(node.left);
                }
                if (node.right != null) {
                    Q.add(node.right);
                }
            }
        }

        return root;
    }
}

var connect = function (root) {
    if (root == null) {
        return root;
    }
    let Q = [];
    Q.push(root);
    while (Q.length > 0) {
        let size = Q.length;
        for (let i = 0; i < size; i++) {
            let node = Q.shift();
            if (i < size - 1) {
                node.next = Q[0];
            }
            if (node.left != null) {
                Q.push(node.left);
            }
            if (node.right != null) {
                Q.push(node.right);
            }
        }
    }
    return root;
};

import collections

class Solution:
    def connect(self, root: "Node") -> "Node":
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)
            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    Q := []*Node{root}
    for len(Q) > 0 {
        size := len(Q)
        for i := 0; i < size; i++ {
            node := Q[0]
            Q = Q[1:]
            if i < size-1 {
                node.Next = Q[0]
            }
            if node.Left != nil {
                Q = append(Q, node.Left)
            }
            if node.Right != nil {
                Q = append(Q, node.Right)
            }
        }
    }
    return root
}

Algorithm

1️⃣

Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

2️⃣

Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве.

3️⃣

Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())

{

size = Q.size()

for i in range 0..size

{

node = Q.pop()

Q.push(node.left)

Q.push(node.right)

}

}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎