二叉树中最大距离处的两个节点

Question

我被问题的修改版本（找到位于二叉树中距离k处的两个节点）卡住了。

我试图定义两个节点之间的距离，我相信它是沿树枝从节点n1到节点n2所需的最小节点数。

那么继续这个假设，我得出了一种情况，我相信我需要知道每个节点是否位于根的左侧或右侧。情况1：如果n1和n2在不同侧，那么我爬到根部（距离等于节点n1的深度 - 假设n1在左边），然后向下跑到右边节点n2（距离等于n2的深度）。因此，两个节点n1，n2之间的最大距离是它们在根的不同侧的深度的总和。情况2：如果n1和n2在同一侧，我找到树的层次结构中两个共同的祖先，并重复相同的过程，考虑祖先的根，就像我在案例1中所做的那样。 最小距离将是它们根深度的总和 - 共同祖先的深度的2倍。

现在，问题在于，我最终会为每对节点直截了当地做这件事。如果我知道一对距离超过这个距离的节点，但我怎样才能优化它以不检查一对呢？

请建议解决方案的其余部分。

Answer 1

@Benjamin，谢谢你的指针。 topcoder教程链接在您提出的链接中的答案之一，完全解释了问题以及多种解决方法。

这是一个纯LCA问题，我能解决它。我想在这里也包括tuorial链接。

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor

Answer 2

与Diameter of a Binary Tree相同的问题（请参见自下而上的方法），它定义为树中两棵树叶之间最长路径上的节点数。在你的情况下，你也必须找出节点。