Вопрос:
Учитывая root бинарного дерева, сведите дерево в связный список:

  • «Связанный список» должен использовать тот же класс TreeNode, в котором дочерний указатель right указывает на следующий узел в списке, а дочерний указатель left всегда равен null.
  • Связанный список должен быть в том же порядке, что и обход в прямом порядке бинарного дерева.

Пример 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Решение:

В заданном вопросе мы должны преобразовать двоичное дерево в отсортированный связанный список.

В этом случае мы должны применить BFS и вывести все узлы с правой стороны и указать левое поддерево на null.

Итак, сначала мы создадим новый указатель prev, который будет указывать на null.

TreeNode* prev = nullptr;

Мы проверим, пусто бинарное дерево или нет. Если да, то мы вернемся.

if(!root) 
    return;

Теперь мы вызовем функцию flatten() для правого и левого поддеревьев.

flatten(root -> right);
flatten(root -> left);

Мы укажем левое поддерево на null, а правое поддерево — на указатель prev, чтобы напечатать список справа от корня.

root -> left = nullptr; 
root -> right = prev;

Последний шаг — сделать указатель prev корнем двоичного дерева.

prev = root;

Ниже приведена полная реализация задачи:

Спасибо за прочтение!

S.