我遇到问题的修改版本（找到位于二叉树中距离k的两个节点） .
我试图定义两个节点之间的距离，我相信它是沿着树枝从节点n1到节点n2所需的最小节点数 .
继续这个假设，我到达了一种情况，我认为我需要知道每个节点是否在根的左侧或右侧 .
情况1：如果n1和n2在不同的一侧，那么我爬到根（距离等于节点n1的深度 - 假设n1在左边）然后我向下跑到右边节点n2（距离等于n2的深度） ） . 因此，如果它们位于根的不同侧，则两个节点n1，n2之间的最大距离是它们的深度的总和 .
情况2：如果n1和n2在同一侧，我在树层次结构中找到两个共同的祖先，并重复相同的过程，考虑到祖先的根，就像我在案例1中所做的那样 . 最小距离将是它们的深度来自根 - 是共同祖先深度的2倍 .
现在，问题是，我最终直截了当地为每对节点做这个 . 我可以优化它，如果我知道一对节点远远超过这个但是怎么样？
请建议其余的解决方案 .
2 回答
与Diameter of a Binary Tree相同的问题（参见自下而上的方法），它被定义为树中两个叶子之间最长路径上的节点数 . 在您的情况下，您还必须找到节点 .
@Benjamin，谢谢你的指针 . topcoder教程链接在您建议的链接中的一个答案中完整地解释了问题和解决它的多种方法 .
这是一个纯粹的LCA问题，我能够解决它 . 我想在这里也包括图案链接 .
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor