В сегодняшней задаче мы собираемся свести двоичное дерево к связному списку.
Это довольно прямая проблема. Нам нужно будет перебрать каждый узел и отслеживать каждый узел в нашем двоичном дереве. Мы делаем это, вызывая функцию поиска в глубину нашего дерева. Это будет предварительный обход, так как мы хотим, чтобы все было в последовательном порядке.
После того, как мы проведем поиск по нашему дереву, у нас останется массив, содержащий узлы (и поддеревья) нашего исходного бинарного дерева. Теперь нам нужно соединить эти узлы в бинарное дерево, представляющее собой связанный список. Это означает, что наше дерево может иметь только правильные дочерние узлы. Теперь мы пройдемся по нашему массиву заказов. В каждом индексе мы устанавливаем левый дочерний узел равным нулю, а правый дочерний узел устанавливаем равным следующему узлу в нашем массиве заказов.
Давайте посмотрим пример:
