c++ - 查找树中两个节点的最小公共(public)祖先

Question

我在面试中被问到这个问题，虽然我知道如何解决这个问题，但我没有回答。我不知道该怎么做的原因是因为问题是这样给我的:

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

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

面试官要我找出a和b的最不共同祖先。我问我们是否得到了指向我们正在搜索的树的根的指针，他说没有。所以我对如何解决这个问题感到困惑，因为我什至没有一棵树可以使用。

在这种情况下是否有可能找到最不共同的祖先？我是否应该假设我们得到了一个全局 Node* ，它是树的根之类的？有没有人遇到过类似的问题？

Answer 1

不，这是不可能的。要回答给你的问题，你需要能够找到一个节点和它的祖先之间的路径。为此，您需要将节点作为起点并在每个节点中引用父节点。或以祖先(或祖先的祖先)为起点并引用每个节点中的子节点。