时间复杂性 - 找到所有最深的叶子的最低公共祖先的算法

Question

这是我今天遇到的问题陈述。

给定二叉树，找到所有最深的叶子的最低常见祖先。

我提出了一个正确的算法，但我想确认这种方法的运行时间。

算法如下：

1. 遍历树，找到树的最深级别 dmax 。
2. 遍历树并在深度 dmax 中找到所有叶子。
给出 LCA（A，B，C） = LCA（LCA（A，B），C） < /强>，遍历在步骤2中找到的所有节点并计算LCA。

lca（a，b） 的子程序很简单。从 a 开始，一直到root，并将每个访问的节点存储在hashset中。然后，从 b 开始，上升，直到找到一个包含在桥接中的节点。

我知道算法的前两个步骤都是 O（n），其中n对应于树中的节点数。但是，我不确定最后一步。

lca（a，b） 子程序具有线性复杂性。但是在最糟糕的情况下，有多少节点可以在步骤2中找到？。

直观地，我认为它必须远远低于N节点。

Answer 1

在@rick decker解释中，您可以在一个案例中具有 $ n / 2 $ 叶子。在这种情况下，步骤3是 $ o（n \ log n）$ 。 这篇文章显示最坏的情况。考虑一棵树 $ t $ 由一个 $ n / 2 $ 节点作为链条底部的平衡树附加。这为每个叶子深度 $ n / 2 + \ log_2（n）=theta（n）$ with $ n / 4 $ 在深度 $ \ theta（n）$ 我们有 $ \ theta（n ^ 2） $ 运行时在这种情况下，步骤3。这是渐近的最坏情况，因为我们有 $ n $ 节点，在max depth $ n $ 。

有更好的方法来做这件事。让我们定义一个函数 $ f $

$ f（v）=begin {案例} v＆\ text {if} \ quad \ texttt {height}（v.left）=texttt {height}（v.right）\\ f（v.left）＆\ text {if} \ quad \ texttt {height}（v.left）> \ texttt {height}（v.right）\\ f（v.right）＆\ text {if} \ quad \ texttt {height}（v.left）<\ texttt {height}（v.right） \结束{案例} $

如果节点的子节点 $ v $ 是相同的，那么明确 $ v $ SPAN>是子树最深点的LCA植根于 $ v $ 。如果左子树更高，那么我们希望子树最佳节点的LCA植根于 $ v.left $ ，因为它们比最深节点更深植根于 $ v.right $ 。相同的逻辑随后遵循 $ v.right $ 较高。

$ \ texttt {height} $ 和 $ f（v）$ 可以在线性时间计算在 $ t $ 中的遍历遍历。

调用 $ f（root）$ 应返回树中最深节点的LCA。

Answer 2

好吧，我不知道你打算的意图“远小于”，但很明显，你可以在最大深度上留下 $ n / 2 $ 叶子：拍摄完整的二叉树，例如，具有最低的级别。

Answer 3

我会编写一个函数，每个树计算所有最深节点的最低公共祖先，和树的高度。这很简单：

如果根r没有左或右分支，那么高度为1，共同的祖先是R.如果根r具有左或右分支，则计算该分支的高度和最低公共祖先具有根r的高度较高，但最低的常见祖先是相同的。

如果左和右分支，则计算两个分支的高度和最低公共祖先。如果高度是不同的，那么我们返回（高度+ 1）加上该分支的最低祖先。如果高度是相同的，那么我们返回（高度+ 1），并作为最低的公共祖先。

如果节点的数量是n，则应采用cn步骤使用小常量c.并且由于我们必须访问每个节点n（至少知道它没有分支），因此不能改进。