Вопрос:
Учитывая 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.