Шаг за шагом Кратчайший путь от исходного узла к целевому узлу в двоичном дереве

Опубликовано: 20 Сентября, 2022

Дан корень бинарного дерева и два целых числа startValue и destValue, обозначающие начальный и конечный узлы соответственно. Задача состоит в том, чтобы найти кратчайший путь от начального узла к конечному узлу и вывести путь в виде направлений, приведенных ниже.

  1. Переход от одного узла к его левому дочернему узлу обозначается буквой «L» .
  2. Переход от одного узла к его правому дочернему узлу обозначается буквой «R» .
  3. Чтобы перейти от узла к его родительскому узлу , используйте букву «U» .

Примеры:

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

              5
          /      
       1          2
    /          /    
  3        6         4

Output: “UURL” 
Explanation: The shortest path is: 3 → 1 → 5 → 2 → 6.

Input: root = [2, 1], startValue = 2, destValue = 1

            2
          /
       1

Output: “L”
Explanation: The shortest path is: 2 → 1.

Подход: Самый простой способ решить эту проблему — использовать LCA (самый низкий общий предок) бинарного дерева. Выполните следующие шаги, чтобы решить данную проблему.

  • Примените LCA , чтобы получить новый корень.
  • Получите Path от нового корня до start и dest .
  • Объедините startPath и destPath и обязательно замените char startPath на 'U' .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(3N), потому что выполняется три обхода.
Вспомогательное пространство: O(1)

Эффективный подход: этот подход основан на реализации, но LCA в нем не используется. Выполните следующие шаги, чтобы решить данную проблему.

  • Создавайте направления как для начала, так и для пункта назначения от корня.
  • Скажем, мы получаем «LLRRL» и «LRR» .
  • Удалить общий путь префикса.
  • Убираем «L» , и теперь начальное направление — «LRRL» , а пункт назначения — «RR» .
  • Замените все шаги в начальном направлении на «U» и добавьте целевое направление.
  • Результат «УУУУ» + «RR» .

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N)
Вспомогательное пространство: O (1), если пространство стека рекурсии игнорируется.

РЕКОМЕНДУЕМЫЕ СТАТЬИ