Вопрос:

При рекурсивном поиске максимальной суммы пути добавьте левое или правое направление двоичного дерева.

python binary-tree binary-search-tree

16 просмотра

1 ответ

11 Репутация автора

Я создаю код Python для определения наибольшего (сумма узлов) пути двоичного дерева. При повторении через дерево я хотел бы добавить направление пути («l» или «r» для левого и правого соответственно) в список, который можно вызвать позже в коде.

До сих пор мне удалось правильно получить самый большой путь (максимальная сумма узлов) и первое направление пути, но не полный путь.

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

def sum_max_path(root):

    if not root:
        return

    if root.left is None:
        l_sum = 0
    else:
        l_sum = sum_max_path(root.left)

    if root.right is None:
        r_sum = 0
    else:
        r_sum = sum_max_path(root.right)

    if l_sum > r_sum:
        root.list.append("l")
        return root.value + l_sum
    elif l_sum < r_sum:
        root.list.append("r")
        return root.value + r_sum
    else:
        root.list.append("l")
        return root.value + l_sum

    return root.value + max(l_sum, r_sum)

return sum_max_path(root), root.list

Выход этого:

The total value in this path is: 8
The largest value path is: ['l']

Что бы я хотел, чтобы на выходе было:

The largest value path is ['l', 'r', 'l'] 

(Очевидно, в зависимости от того, как долго путь основан на сгенерированном дереве).

Автор: Neelhtak Источник Размещён: 11.08.2019 06:51

Ответы (1)


0 плюса

163031 Репутация автора

Не храните путь статически, вместо этого передайте его и возвращайте его после каждого рекурсивного вызова:

def max_sum(node, path):
    ls = rs = 0
    lp = rp = path
    if node.left:
        ls, lp = max_sum(node.left, path + ['l'])
    if node.right:
        rs, rp = max_sum(node.right, path + ['r'])
    ls += node.value
    rs += node.value
    return (ls, lp) if ls > rs else (rs, rp)
Автор: georg Размещён: 11.08.2019 07:42
Вопросы из категории :
32x32