在递归查找二叉树的最大路径和时，将其路径向左或向右延伸。

Question

在递归查找二叉树的最大路径和时，将其路径向左或向右延伸。

4

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

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- georg · Accepted Answer

不要静态地存储路径，而是将其传递给每个递归调用并从中返回：
最初的回答

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, []))