Задача средней сложности от Leetcode

Суммирование корневых и конечных чисел - интересная задача от Leetcode. Задача средней сложности и касается бинарных деревьев. Этот пост - объяснение решения проблемы.

Я предполагаю, что вы знакомы с Python и концепцией двоичных деревьев. Если нет, для начала прочтите эту статью.

Проблема

Для двоичного дерева, узлы которого содержат значения 0-9, мы должны найти сумму всех чисел, образованных путями от корня к листу. Лист - это узел, у которого нет дочерних узлов. В двоичном дереве путь от корня к листу всегда уникален. Вот ожидаемое поведение требуемого решения:

В дереве слева результат будет 25. 25 - это сумма 12 и 13, двух чисел, образующихся при запуске с 1 и посещении каждого листа. В дереве справа на выходе будет 1026, поскольку это сумма трех чисел 495, 491 и 40.

Наблюдения и выводы

  1. Чтобы построить число, мы обходим дерево от корня к листу, добавляя цифры, где самая значимая цифра находится в корне, а младшая цифра - в конце. Мы посещаем некоторые листья перед другими узлами, которые ближе к корню. Это говорит о том, что будет полезен поиск в глубину.
  2. Построение чисел является инкрементным и в некотором роде аналогичным: единственная разница между 495 и 491 (из дерева справа) - это последняя цифра. Если мы удалим 5 и вставим на его место 1, у нас будет следующий требуемый номер. Число по существу состоит из цифры листа, добавленной ко всем цифрам в узлах-предках. Таким образом, числа в одном поддереве имеют общие цифры.
  3. Наконец, обратите внимание, что эта проблема связана с деревом, поэтому полезно рекурсивное решение.

Решение

Мы можем сделать pre-order обход дерева, при котором мы постепенно создаем число и воспользуемся тем фактом, что числа, образованные узлами в одном поддереве, имеют общие цифры. Когда мы закончили формировать числа в поддереве, мы можем вернуться назад и перейти к другому поддереву.

Давайте создадим Solution класс, охватывающий наше решение.

Сигнатура метода, данная нам в задаче, имеет один аргумент: root, который имеет тип TreeNode. Класс TreeNode выглядит следующим образом (из Leetcode):

Из наблюдения № 2 обратите внимание, что добавление цифры узла к его предкам может быть достигнуто путем перемещения всех цифр числа, образованного предками, на 1 место вправо и добавления цифры текущего узла. Цифры можно перемещать, умножив число, образованное предками, на 10 (поскольку мы находимся в системе счисления по основанию 10). Например:

495 = 49 x 10 + 5

Таким образом, мы можем отслеживать текущие цифры целого числа. Это важно, потому что нам не потребуется дополнительное пространство для хранения для ввода большего размера. Мы можем передать это значение в самом параметре функции. Поскольку указанная сигнатура метода может иметь только один параметр, давайте создадим sum_root_to_leaf_helper метод.

Мы можем думать о методе sum_root_to_leaf_helper рекурсивно и обрабатывать каждый узел по-разному в зависимости от того, является ли он листом.

  • Если узел является листом, мы хотим добавить его цифру к нашим текущим цифрам, переместив все остальные цифры вправо. Мы также хотим вернуть это значение (поскольку отсюда мы вернемся назад).
  • Если это не лист, мы хотим добавить цифру к нашим текущим цифрам, сдвинув все остальные цифры вправо. Мы также хотим продолжить построение числа, перемещаясь вниз по левому и правому поддеревьям этого узла.

Если текущий узел None, мы можем просто вернуть 0, потому что он не считается.

Таким образом, наш sum_root_to_leaf_helper метод будет таким:

Мы используем значение по умолчанию для частичной суммы, равное 0.

В нашем основном методе мы хотим включить метод sum_root_to_leaf_helper как вложенный метод и просто передать параметр узла. Наконец, вот как выглядит наше решение:

Алгоритмическая сложность

Когда мы придумываем решение, важно анализировать его алгоритмическую сложность не только для оценки его производительности, но и для определения областей, требующих улучшения, и размышления о наших навыках решения проблем. Мы всегда должны задавать вопрос: можем ли мы сделать лучше, чем X? Где X - текущая сложность нашего решения.

Время:

Наше решение представляет собой модификацию обхода предварительного заказа с поиском в глубину, при котором мы посещаем все узлы ровно один раз и выполняем тривиальное вычисление (перемещение цифр путем целочисленного умножения). Таким образом, наша среда выполнения - это просто O(N), где N представляет количество узлов в данном дереве. Решение лучше, чем O(N), кажется невозможным, потому что для построения числа из цифр нам нужно знать все цифры (и, таким образом, посетить все узлы).

Космос:

Что касается хранилища, мы несем большие затраты на стек вызовов рекурсии, который накапливается по мере того, как наш sum_root_to_leaf_helper вызывает себя. Эти вызовы вызывают наращивание, когда один ждет завершения другого.

Максимальный стек вызовов зависит от высоты двоичного дерева (поскольку мы начинаем обратное отслеживание после посещения листа), что дает сложность O(H), где H - высота двоичного дерева. В худшем случае двоичное дерево искажается в любом направлении и, следовательно, H = N. Следовательно, сложность пространства в наихудшем случае равна O(N).

Вы можете прочитать эту статью, чтобы узнать больше о стеках вызовов рекурсии.

Можно добиться большего, чем O(N), используя обход предварительного заказа Морриса. Основная идея - временно связать узел и его предшественник. Вы можете прочитать больше об этом здесь".

Вывод

Надеюсь, этот пост помог! Пожалуйста, дайте мне знать, если у вас есть какие-либо отзывы, комментарии или предложения, ответив на это сообщение.

Благодарности

Адвай, Кевин, Луи за просмотр этого сообщения и Яншун за идею добавления его в качестве сообщения в блоге.