binary-tree - 二叉树中距离最大的两个节点

Question

我遇到了问题的修改版本(在二叉树中查找位于距离 k 处的两个节点)。

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

继续这个假设，我遇到了一种情况，我相信我需要知道每个节点是在根的左边还是右边。

案例1:如果n1和n2在不同的一侧，那么我爬到根部(距离等于节点n1的深度-假设n1在左边)然后我跑到右边的节点n2(距离等于n2的深度)。因此，如果两个节点 n1 和 n2 位于根的不同侧，则它们之间的最大距离是它们的深度之和。

案例 2:如果 n1 和 n2 在同一侧，我会在树层次结构中找到一个共同的祖先，并重复相同的过程，将祖先视为根，就像我在案例 1 中所做的那样。
最小距离将是它们与根的深度之和 - 共同祖先深度的 2 倍。

现在，这个问题是，我最终坦率地为每一对节点都这样做。如果我知道一对节点的距离超过这个，我可以优化它以不检查一对节点，但是如何？

请提出解决方案的其余部分。

Answer 1

与 Diameter of a Binary Tree 相同的问题(参见自下而上的方法)，它被定义为树中两个叶子之间最长路径上的节点数。在您的情况下，您还必须找出节点。