在一棵树中查找两个节点的最近公共祖先

Question

我在一次面试中被问到了这个问题，虽然我知道如何解决它，但我还是没能回答出来。原因是问题是这样给我的：

class Node{
      int val;
      Node *left, *right;
};

int LCA(int a, int b){
     //your code here
}

面试官要求我找到a和b的最近公共祖先。我问是否给出了我们正在搜索的树的根指针，他说没有。因此，我不知道该如何解决这个问题，因为我甚至没有树可供使用。

在这种情况下是否可能找到最近公共祖先？我应该假设我们被给予了一个作为树根的全局Node*或其他东西吗？有人遇到过类似的问题吗？

- Bob John

---

如果没有给你一棵树，你如何对一棵树进行操作？也许LCA()函数应该是类的成员函数？ - Brad S.

如果a和b都是Node，而且返回的祖先也是Node，那么应该不是FindLCA(int a, int b)，而是Node LCA(Node a, Node b)，对吗？ - chiliNUT

@chiliNUT 我也是这么想的。尽管我问了多次，面试官还是坚持认为这是“正确”的问题格式。我想我的怀疑是正确的，他错了。然而，即使有两个节点，如果没有根节点，你如何找到它们的LCA呢？ - Bob John

面试官是错误的。 - n. m.

我认为一个更有趣的问题是，如何证明面试官是错的，通过展示没有根节点或某种父链接节点，问题无法解决。 - greatwolf

Answer 1

不可能。为了回答你所提出的问题，你需要能够找到一个节点和它的祖先之间的路径。为此，你需要以节点作为起点，并在每个节点中引用其父节点。或者以祖先（或祖先的祖先）作为起点，并在每个节点中引用其子节点。

- Sonic

Answer 2

从您描述的面试互动方式来看，我怀疑这是一个巧妙的问题。可能只是为了测试您是否坚持不断地询问澄清问题。如果换成我，得到没有根节点的反馈后，我会问是否有其他方式将节点值彼此相关。如果节点有数学关系，则解决LCA问题时可能不需要根节点。

另一种策略是确定节点如何插入、删除和查找。也就是说，弄清楚哪些API可用。您可能已经发现面试官提供了父API。

有时候，面试就像是冒险游戏，面试官真正希望看到的是你走出曲折的迷宫（无论多么不公平）。

- jxh