给定 BST 中的 3 个节点，检查一个是否是另一个的祖先，第三个是否是后代 - 为什么这需要 O(h) 时间？

Question

我正在解决给定 BST 和 three nodes 的问题，我们想确定：“是否 nodeOne 或 nodeThree 是 nodeTwo 的祖先，另一个节点是 nodeTwo 的后代。"

例如如果 nodeOne 是 nodeTwo 的祖先，则检查 nodeThree 是否是 nodeTwo 的后代。 否则如果 nodeThree 是 nodeTwo 的祖先，则检查 nodeOne 是否是 nodeTwo.

的后代

这是非常简单的几个检查，我们将简单地搜索 BST 检查上面的内容，即首先如果 nodeOne 是 nodeTwo 的祖先，如果不是，然后检查 nodeThree 是否是 nodeTwo 的祖先，然后以 True 为准，我们将检查另一个节点是否是 nodeTwo 的后代。

在我看来，这需要 O(log(n)) time，其中 n 是从第一个节点到最后一个节点的节点数（第一个和最后一个是三个节点之一）- 因为我们知道三个节点的值，我们每次遍历 BST 时都可以消除一半的树，但是在解决方案中它说它需要 O(h) time，其中 h 是树的高度 。

有人可以澄清一下为什么确实是 O(h) 时间吗？

我省略了这个算法，因为我认为它没有必要，但它本质上是使用递归遍历从 nodeOne 开始然后是 nodeThree 的树，如果 nodeOne 不是 nodeTwo 的后代。

Answer 1

树的高度是从树根到叶子的最长路径的长度。 BST 中的搜索沿着从根节点到叶子的某些路径下降。

这不会超过搜索路径上的节点数，而这又不会超过树的高度 - 因此 O(h).

已添加：

你也可以一次找到答案。寻找nodeThree，如果沿途遇到nodeOne和nodeTwo，记录下来。

• 如果是这样，并且按照这个顺序，您就得到了肯定的答案。
• 如果您只找到其中​​之一，或两者都找到但顺序错误，则答案是否定的。
• 否则，从nodeThree继续寻找，这次的目标是nodeOne。
  • 如果您在找到 nodeOne 之前遇到 nodeTwo，则结果为阳性。
  • 否则就是你没有找到nodeOne，或者前面没有找到nodeTwo，结果是否定的。