Пошаговые инструкции от узла бинарного дерева к другому решению LeetCode

Постановка задачи: пошаговые инструкции от узла двоичного дерева к другому решению LeetCode. Вам дан корень двоичного дерева с n узлами. Каждому узлу однозначно присваивается значение от 1 до n. Вам также дается целое значение startValue, представляющее значение начального узла s, и другое целое значение destValue, представляющее значение пункта назначения…

Подробнее

Обход вертикального порядка двоичного дерева Решение LeetCode

Постановка задачи Обход двоичного дерева в вертикальном порядке Решение LeetCode говорит: Учитывая корень двоичного дерева, вычислите обход двоичного дерева в вертикальном порядке. Для каждого узла в позиции (строка, столбец) его левый и правый потомки будут в позициях (строка + 1, столбец — 1) и (строка + 1, столбец + 1) соответственно. …

Подробнее

Суммирование корней и листовых чисел Решение LeetCode

Постановка задачи Суммирование чисел от корня до листа Решение LeetCode говорит: Вам дан корень двоичного дерева, содержащего только цифры от 0 до 9. Каждый путь от корня к листу в дереве представляет собой число. Например, путь от корня к листу 1 -> 2 -> 3 представляет число 123. Возвращает общую сумму всех чисел от корня к листу. Тест …

Подробнее

Решение LeetCode для обхода двоичного дерева по порядку

Постановка задачи: Неупорядоченный обход двоичного дерева Решение LeetCode Учитывая корень двоичного дерева, вернуть неупорядоченный обход значений его узлов. Пример 1: Ввод: root = [1,null,2,3] Вывод: [1,3,2] Пример 2: Ввод: root = [] Вывод: [] Пример 3: Ввод: root = [1] Вывод: [1] Ограничения: количество узлов в …

Подробнее

Преобразование двоичного дерева в связанный список Решение LeetCode

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

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

 

Пример 1:

Преобразование двоичного дерева в связанный список Решение LeetCodeВходной сигнал:

 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 прав узел поддерева.

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

 

Преобразование двоичного дерева в связанный список Решение LeetCode

Преобразование двоичного дерева в связанный список Решение LeetCode

Решение 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

Диаметр N-арного дерева Решение LeetCode

Постановка задачи: диаметр N-арного дерева Решение LeetCode. Имея корень N-арного дерева, вам нужно вычислить длину диаметра дерева. Диаметр N-арного дерева — это длина самого длинного пути между любыми двумя узлами дерева. Этот путь может быть, а может и нет…

Подробнее

Наименьший общий предок решения Leetcode для двоичного дерева

Постановка задачи Наименьший общий предок двоичного дерева Решение LeetCode — «Наименьший общий предок двоичного дерева» утверждает, что заданы корень двоичного дерева и два узла дерева. Нам нужно найти наименьшего общего предка этих двух узлов. Самый низкий общий…

Подробнее

Заполнение следующих правильных указателей в каждом узле Решение Leetcode

Постановка задачи Заполнение следующих правых указателей в каждом узле Решение LeetCode — «Заполнение следующих правых указателей в каждом узле» утверждает, что задан корень идеального двоичного дерева, и нам нужно заполнить каждый следующий указатель узла его следующим правым узлом. Если рядом нет…

Подробнее

Удалить узлы и вернуть решение Forest Leetcode

Постановка задачи Решение LeetCode «Удалить узлы и вернуть лес» — «Удалить узлы и вернуть лес» утверждает, что задан корень двоичного дерева, где каждый узел имеет отдельное значение. Нам также дан массив to_delete, где нам нужно удалить все узлы со значениями, содержащимися в …

Подробнее

Решение для восстановления двоичного дерева поиска Leetcode

Постановка задачи Восстановление двоичного дерева поиска Решение LeetCode — «Восстановление двоичного дерева поиска» утверждает, что задан корень двоичного дерева поиска, где значения ровно двух узлов поменяны местами по ошибке. Нам нужно восстановить дерево без изменения его структуры. Пример: Ввод: root = [1,3,null,null,2] Вывод: [3,1,null,null,2] …

Подробнее

Translate »