我们如何找到二叉树的中心? 什么是最有效的算法。虽然二叉树的中心将是对应于树直径的路径的中点。我们可以在不知道实际路径的情况下求出树的直径,有没有类似的求二叉树中心的技术?
最佳答案
如果你知道直径:D
你知道树的最大深度:M
然后你的中心将在最深路径上的第 (M-(D/2)) 个节点(从根开始)。(它可能是 M - (D-1)/2 取决于奇偶校验,你需要检查自己)
如果从根到叶的路径多于 1 条,且有 M 个节点,则中心就是根。 (仅当最长路径通过根时才成立)
编辑:
回答你的问题。
如果它不通过根。让我们取直径上的第 D/2 个节点,它仍然位于直径路径的最长边(在所有情况下,这是从根到叶的最长路径)。因此 M-D/2 仍然从根代表这一点。
从根节点取 M-D/2nth 与从最长路径的叶子节点取 D/2nth 是一样的。
我够清楚吗?您可能只想绘制它来检查它。
关于二叉树的中心,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7094832/