117. Populating Next Right Pointers in Each Node II

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) return root;
    const Q = [];
    Q.push(root);
    while (Q.length > 0) {
        const size = Q.length;
        for (let i = 0; i < size; i++) {
            const node = Q.shift();
            if (i < size - 1) {
                node.next = Q[0];
            }
            if (node.left) Q.push(node.left);
            if (node.right) Q.push(node.right);
        }
    }
    return root;
};

class Solution:
    def connect(self, root: Optional["Node"]) -> Optional["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 := list.New()
    Q.PushBack(root)
    for Q.Len() > 0 {
        size := Q.Len()
        for i := 0; i < size; i++ {
            front := Q.Front()
            node := front.Value.(*Node)
            Q.Remove(front)
            if i < size-1 {
                node.Next = Q.Front().Value.(*Node)
            }
            if node.Left != nil {
                Q.PushBack(node.Left)
            }
            if node.Right != nil {
                Q.PushBack(node.Right)
            }
        }
    }
    return root
}

Explanation

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.

😎