2

我在一次编程面试中得到了这个问题。随意考虑如何回答它。

给你一个二叉树（不是二叉搜索树）的根节点，其中每个节点都包含一个整数值，并且没有值出现两次。您还获得了两个值val1and val2（可能在树中也可能不在树中。）如果两者都在树中，则返回包含这两个值的两个节点中最小共同祖先的节点。如果不是，则返回 null。

假设每个节点都可以访问左右子节点。您可以附加节点结构，但不能将父节点附加到每个节点。您的算法应该在小于 O(N^2) 的时间内运行，其中 N 是树中的节点数。

注意：虽然它类似于著名的最不常见祖先问题，但这一问题的局限性使其并不完全相同。

4

1 回答 1

0

我不明白你为什么会考虑 O(N 2 )，除非我误解了这个问题。以下解决方案是前序遍历，因此每个节点最多访问一次：

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);
}

我想一些解释是有序的，但也许因为它只是一个脑筋急转弯，最好把代码留在那里，看看人们是怎么理解的。（而且我也没有彻底测试它，让它看起来更像是一次采访。）

这不是我在采访中使用过的问题，如果有人提出上述代码作为答案，我不确定我会做什么。但后来我一直不确定我会雇用自己。

于 2012-10-28T03:45:48.390 回答