python - 在递归查找最大路径和时，追加二叉树的左或右方向

Question

我正在创建 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'] 

(显然取决于生成树的路径有多长)。

Answer 1

不要静态存储路径，而是将其传递给每个递归调用并从中返回:

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)

完整示例:

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


tree = Node(
    1,
    Node(
        9,
        Node(2),
        Node(3)
    ),
    Node(
        8,
        Node(2),
        Node(
            5,
            Node(3),
            Node(2)
        )
    )
)


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)


print(max_sum(tree, []))