Преобразование двоичного дерева в связанный список Решение LeetCode говорит, что - Учитывая root бинарного дерева, сгладьте дерево в «связный список»:

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

 

Пример 1:

Входной сигнал:

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

Вывод:

 [1,null,2,null,3,null,4,null,5,null,6]

Пример 2:

Входной сигнал:

 root = []

Вывод:

 []

Пример 3:

Входной сигнал:

 root = [0]

Вывод:

 [0]

 

АЛГОРИТМ –

ИДЕЯ –

• Чтобы сгладить двоичное дерево, мы сначала найдем самый правый элемент левого поддерева, и после того, как мы получим самый правый элемент, мы свяжем правый указатель этого узла с правым поддеревом данного дерева.
• На шаге 2 мы свяжем правый указатель корневого узла с левым поддеревом и установим левое поддерево как нулевое.
• На шаге 3 теперь наш корневой узел является узлом правого поддерева, тот же процесс произойдет с этим узлом, и процесс будет продолжаться до тех пор, пока все левые части не станут нулевыми.

Подход к сведению двоичного дерева к решению Leetcode для связанного списка —

– Сначала я запущу цикл, т.е. while(root != null), затем возьму две переменные и сохраним левое поддерево.

- затем проверит проверку самого правого узла левого поддерева, используя while(k.left != null), и свяжет этот узел с правым поддеревом, используя (k.right = root.right).

- затем свяжите правый указатель корневого узла с левым поддеревом (root.right = left) и установите левый указатель корневого узла как null (root.left = null) и обновите ( root = root.right ), так что теперь root прав узел поддерева.

– этот процесс будет продолжаться до тех пор, пока все части левого поддерева не станут правым поддеревом. Следовательно, бинарное дерево будет сплющено.

 

Решение Python:

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        while(root):
            
            if root.left:
                
                k = root.left
                temp = root.left
            
            
                while(k.right):
                    k = k.right
            
                k.right = root.right
            
                root.right = temp
            
                root.left = None
            
            root = root.right

Java-решение:

class Solution {
    public void flatten(TreeNode root) {       
        while (root != null) {
            if (root.left != null) {
                TreeNode k = root.left;
                TreeNode temp = root.left;
                while (k.right != null) k = k.right;
                k.right = root.right;
                root.right = temp;
                root.left = null;
            }
            root = root.right;
        }
    }
}

Временная сложность: O (N)

Космическая сложность: O (1)

Поскольку мы прошли только один раз, временная сложность будет o(n).

и поскольку мы не занимали никакого дополнительного места, объемная сложность будет равна o(1) постоянному дополнительному пространству.

Аналогичный вопрос - https://www.tutorialcup.com/interview/linked-list/flattening-linked-list.htm