Найти путь к указанному узлу в двоичном дереве (Python)

Question

У меня проблемы с вычислением пути от корня к указанному узлу в двоичном дереве (это конкретно о Python-решении этой проблемы).

Вот пример. Учитывая приведенное ниже двоичное дерево, если я укажу узел, значение которого равно 4, я хочу вернуть [1, 2, 4]. Если я укажу узел, значение которого равно 5, я хочу вернуть [1, 2, 5].

       1
     /  \
   2      3
 /  \
4    5

Вот мое попытанное решение.

class TreeNode:
 def __init__(self, x):
     self.val = x
     self.left = None
     self.right = None

def path(root, k, l=[]):
    if not root:
        return []
    if root.val == k:
        return l

    # Pre-order traversal: Visit root, then left, then right.
    l.append(root.val)
    path(root.left, k, l)
    path(root.right, k, l)
    return l

Теперь, если я запускаю это

>>> a = TreeNode(1)
>>> b = TreeNode(2)
>>> c = TreeNode(3)
>>> d = TreeNode(4)
>>> e = TreeNode(5)
>>> a.left = b
>>> a.right = c
>>> b.left = d
>>> b.right = e
>>> path(a, 4) # should be [1, 2, 4]
[1, 2, 5, 3]

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

Answer 1

Пропажа 4 вызвано тем, что вы никогда не добавляете его. В вашем случае успеха:

if root.val == k:
    return l

… Вам нужно сделать это:

if root.val == k:
    l.append(root.val)
    return l

---

Экстра 3 а также 5 вызваны тем фактом, что вы всегда добавляете значение в промежуточном регистре, даже для узлов, на которые вы собираетесь вернуться.

Это можно исправить, добавив его только в том случае, если один из рекурсивных вызовов возвращает непустой список, но тогда, конечно, у вас будут неупорядоченные узлы. Самое простое решение для этого - преднамеренно вывести узлы из строя:

# Pre-order traversal: Visit root, then left, then right.
if path(root.left, k, l) or path(root.right, k, l):
    l.append(root.val)

… И затем перевернуть список в конце, например, в функции-обертке:

def path2(root, k):
    return list(reversed(path(root, k)))

---

Однако в вашем коде остается еще одна проблема:

def path(root, k, l=[]):

Тот [] это значение по умолчанию для l создается один раз, когда def выполняется, а затем повторно используется при каждом вызове. Это означает, что path2(a, 4) вернет правильный ответ в первый раз, [1, 2, 4], но когда вы вызовете его во второй раз, он будет продолжать добавляться в тот же список и возвращать [1, 2, 4, 1, 2, 4],

Есть несколько идиоматических способов обойти это, но в нашем случае, так как мы уже используем это path2 функция-обертка, мы могли бы просто исправить это там:

def path2(root, k):
    return list(reversed(path(root, k, [])))

... а затем избавиться от значения по умолчанию на path,

---

Тем не менее, вы можете начать с более простой для понимания версии:

def path(root, k):
    if not root:
        return []
    if root.val == k:
        return [root.val]
    res = path(root.left, k)
    if res:
        return [root.val] + res
    res = path(root.right, k)
    if res:
        return [root.val] + res
    return []

(Вы можете сделать это немного короче; я старался изо всех сил, чтобы здесь все было ясно.)

Для многих рекурсивных задач инвертирование их и передача аккумулятора является важной оптимизацией, потому что удаление хвостовых вызовов может удалить одну из ветвей из стека. Даже несмотря на то, что Python не поддерживает TCE, все же стоит научиться делать что-то с помощью хвоста, просто для вашего собственного понимания (и в случае, если вы когда-нибудь напишите код на другом языке, конечно). Но сначала узнайте, как сделать более простую версию, и только потом пытайтесь ее инвертировать.