在二叉树中找到最长路径的算法？

Question

问题:

You are given a rooted binary tree (each node has at most two children). For a simple path p between two nodes in the tree, let mp be the node on the path that is highest (closest to the root). Define the weight of a path w(p) = Σ_u∈p d(u, mp), where d denotes the distance (number of edges on the path between two nodes). That is, every node on the path is weighted by the distance to the highest node on the path.

该问题询问一种算法，该算法在树中的所有简单路径中找到最大权重。我不确定我是否解释正确，但我可以找到从 mp 到最远节点的最长路径吗？我还没有弄清楚哪种算法适合这个问题，但我认为递归是一种方法。同样，我不太理解这个问题，如果有人可以为我“翻译”它并指导我找到解决方案会更好。

Answer 1

假设我们知道 mp。那么权重最高的路径必须从左子树开始到右子树结束(反之亦然)。否则，这条路就不会简单。为了找到开始和结束节点，我们将尽可能深入到相应的子树中，因为每个级别都将 depth 添加到权重中。因此，我们可以直接根据两棵子树的高度计算这条路径的权值(利用等差数列的解析解):

max_weight = height_left * (height_left + 1) / 2 + height_right * (height_right + 1) / 2

要找到穿过整棵树的最大权重路径(无需指定 mp)，只需检查所有节点的该值。即，采用递归算法计算每个子树的高度。当你有一个节点的两个子树高度时，计算最大权重。在所有这些权重中，取最大值。这需要时间与节点数量呈线性关系。

然后回答你的问题:不，它不一定是树中最长的路径。该路径可以有一个非常深的分支，但在另一侧有一个非常浅的分支。这是因为向路径中添加更深一层不仅会增加 1 的权重，还会增加该节点的深度。