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

Question

我被这个问题的修改版本困住了（在二叉树中找到距离为k的两个节点）。

我试图定义两个节点之间的距离，我认为这是沿着树状分支从节点n1移动到节点n2所需的最小节点数。

从这个假设出发，我得到了一个情况，我认为我需要知道每个节点是在根的左边还是右边。

案例1：如果n1和n2位于不同的一侧，那么我爬到根部（距离等于节点n1的深度-假设n1位于左侧），然后向下跑到右侧节点n2（距离等于节点n2的深度）。所以两个节点之间的最大距离n1，n2是它们的深度之和，如果它们在根的不同边上。

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

现在，问题是，我最终对每对节点都直截了当地这样做。我可以优化它不检查一对，如果我知道一对节点的距离比这更远，但如何？

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

Answer 1

与二叉树的直径相同（见自下而上方法），二叉树的直径定义为树中两片叶子之间最长路径上的节点数。在您的情况下，您还必须找到节点。