algorithm - 在二叉树中找到给定两个值的最不常见祖先

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center。
我在节目采访中得到这个问题。想一想你该怎么回答。
给出了一个二叉树的根节点（不是二叉搜索树），其中每个节点都包含一个整数值，并且没有值出现两次还为您提供了两个值val1和val2（可能在树中，也可能不在树中）。如果这两个值都在树中，则返回包含这两个值的两个节点的最小共同祖先节点如果不是，则返回空值。
假设每个节点都可以访问左、右子节点可以附加节点结构，但不能将父节点附加到每个节点您的算法应该在小于o（n^2）的情况下运行，其中n是树中的节点数。
注：虽然它与著名的最不常见的祖先问题相似，但它的局限性使它不完全相同。

最佳答案

我不明白你为什么会考虑o（n2），除非我误解了这个问题。下面的解决方案是预排序遍历，因此最多访问一次每个节点：

struct node* visit(struct node* visited, int p, int q, struct node* sentinel) {
  if (!visited) return visited;
  if (visited->data == p || visited->data == q) {
    struct node* t;
    if ((t = visit(visited->left, p, q, visited))) return t;
    if ((t = visit(visited->right, p, q, visited))) return t;
    return sentinel;
  } else {
    struct node* left = visit(visited->left, p, q, visited);
    struct node* right = visit(visited->right, p, q, visited);
    if (left == visited) return right ? right : sentinel;
    if (right == visited) return left ? left : sentinel;
    return left ? left : right;
  }
}

struct node* lca(struct node* root, int val1, int val2) {
  return visit(root, val1, val2, 0);
}

我想有些解释是有道理的，但也许因为这只是一个脑筋急转弯，所以最好把代码留在那里，看看人们是怎么理解的。（我也没有彻底测试过，让它看起来更像是一次面试。）
这不是我在面试中使用过的问题，我不确定如果有人提出上述代码作为答案，我会做什么但后来我一直不确定自己会不会受雇。

关于algorithm - 在二叉树中找到给定两个值的最不常见祖先，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13105077/