2

プログラミングのインタビューでこの質問を受けました。どう答えるか、自由に考えてみてください。

各ノードに整数値が含まれ、値が 2 回表示されないバイナリ ツリー (バイナリ検索ツリーではない) のルート ノードが与えられます。また、2 つの値が与えられます(ツリーにある場合val1とval2ない場合があります)。両方がツリーにある場合は、これら 2 つの値を含む 2 つのノードの共通祖先であるノードを返します。そうでない場合は、null を返します。

各ノードが左右の子にアクセスできると仮定します。ノード構造を追加することはできますが、各ノードに親を追加することはできません。アルゴリズムは O(N^2) 未満で実行する必要があります。ここで、N はツリー内のノードの数です。

注: これは有名な最小共通祖先問題に似ていますが、この問題には制限があるため、まったく同じではありません。

4

1 に答える 1

0

私が問題を誤解していない限り、なぜあなたが O(N 2 ) を考えるのか理解できません。次のソリューションは事前順序トラバースであるため、各ノードを最大 1 回訪問します。

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 に答える