algorithm - O(N) 时间和 O(1) 空间的二叉树中的每个子树总和？

Question

给定一个二叉树，我想返回最大和子树的根。

最大子树:树的一个子树，其所有节点的总和大于任何其他子树的总和。

编辑:节点值是一个整数。

我可以执行以下操作，这需要 O(n^2)。

1. 计算左子树所有节点的和
2. 计算右子树所有节点的和
3. 如果左子树和右子树的和与根的值大于当前最大和，则将根存入结果
4. 以左子树为根递归调用此函数
5. 以右子树为根递归调用此函数。这将花费 O(n^2)。

我可以将其更改为自下而上的方法，并使用 HashMap 来存储节点到总和的映射，这将使它成为 O(N)，但它会占用 O(N) 的空间。

有没有办法，O(N)时间O(1)空间？

Answer 1

这几乎就是您的解决方案，但需要 O(n) 和 O(h) 内存。您只需访问每个节点一次。

calculateSum(vertex):
    if not vertex:
        return 0    
    sum = calculateSum(left) + calculateSum(right) + vertex.value
    if (sum > max)
        max = sum
    return sum