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

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

不要静态存储路径，而是将其传递给每个递归调用并return它：

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

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

While recursively finding max path sum, append left or right direction of binary tree

python

binary-tree

binary-search-tree