如何在二叉搜索树中找到节点的第n个祖先？

Question

我在面试时被问到这个问题.这是我的O(log n)解决方案.

找到节点的深度.重复搜索,但停在depth - n.

没有第二次通过,有没有办法做到这一点？

Answer 1

在搜索节点时，您可以跟踪从当前节点到根节点的路径中的所有节点。这是一个简单的列表，长度不大于树的深度。一旦找到该节点，它的第 n个祖先就位于列表中的位置length - n处。