二叉树中的每个子树和在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）空间进行计算。在迭代树时。（在这里，h是树的最大高度，它是递归堆栈的大小）。

伪代码：

TreeSum(v):
  if (v == null):
    return 0
  v_sum = TreeSum(v.left) + TreeSum(v.right) + v.value
  # max_sum is some global space variable holding the max_sum.
  # you hold only once such variable.  
  if v_sum > max_sum:
    max_sum = v_sum 
  return v_sum 

完成后，max_value保存最大和的值
如果还需要节点本身，请保留一个额外的变量，该变量是指向相关节点的指针，并与max\u sum一起修改。

其思想是在树上进行后序遍历。首先计算每个子树的和，然后计算根的值
在计算每个子树的总和时，当您找到一个新的“最佳”子树时，还要修改max_sum。

Answer 2

这几乎就是您的解决方案，但需要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