問題
二分木のroot と、p と q をp のq の
- 共通の
祖先は、 2 つの 節の 両方を 自分の 下に 持つ節です。 ここでは、 節は 自分 自身の 祖先でもあると 数えます。 その ため、 片方が もう 片方の 祖先なら、 上に ある ほうが答えです - いちばん近い
共通の 祖先は、 共通の 祖先の うちいちばん深い (根から 遠い ) 節です - 木は
二分探索木とは 限りません。 値の 大きさで 左右を 決める ことは できません - 木の
値は どれも 違います。 pとqは違う値で、 どちらも 必ず木の 中にあります - 返すのは
節ではなく、 その節の値です - 各節は
val(値)、left(左の子)、 right(右の子) を 持ちます。 子が 無い ところは、 Python では None、JavaScript では null、Go では nilです。Go の 節は TreeNodeで、Val、Left、Rightと大文字で 始まります - 節の
数は 2 以上 500 以下、 値は どれも -1000 以上 1000 以下です
例では、null です。
入力と出力の例
例 1
2 は 11 の
入力
root = [6, 15, 3, 7, 11,
null, 9, null, null, 2, 13]
p = 2
q = 7出力
15例 2
13 は 11 の
入力
root = [6, 15, 3, 7, 11,
null, 9, null, null, 2, 13]
p = 11
q = 13出力
11例 3
-4 は
入力
root = [0, -5, 8, null, -4]
p = -4
q = 8出力
0面接での聞かれ方
面接では、
- 「二分木の 2 つの
節の、 いちばん近い 共通の 祖先を 返してください」 - 書き始める
前に 「片方が 見つからない ことは ありますか？」 「値が 重なる ことは ありますか？」と 条件を 確かめると、 よい 印象になります - 書き終えた
あとに 「片方が 木に 無いかもしれないなら、 どこを 変えますか？」 「二分探索木なら、 もっと 速く できますか？」と 広げて 聞かれます - 「各節が
親への つながりを 持っていたら どう 解きますか？」と、 データの 持ち方を 変えて 聞かれる こともあります
この
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
まず浮かぶのは、p までのq までの
段 2
1 回のp か q が
段 3
関数は、p か q なら、
段 4
自分のp か q の
解答
Python
Python
def common_ancestor(root, p, q):
return find(root, p, q).val
def find(n, p, q):
if n is None:
return None
if n.val == p or n.val == q:
return n
a = find(n.left, p, q)
b = find(n.right, p, q)
if a and b:
return n
return a or bJavaScript
JavaScript
function commonAncestor(
root, p, q
) {
return find(root, p, q).val;
}
function find(n, p, q) {
if (n === null) {
return null;
}
const v = n.val;
if (v === p || v === q) {
return n;
}
const a = find(n.left, p, q);
const b = find(n.right, p, q);
if (a && b) {
return n;
}
return a || b;
}Go
Go
func commonAncestor(
root *TreeNode, p, q int,
) int {
return find(root, p, q).Val
}
func find(
n *TreeNode, p, q int,
) *TreeNode {
if n == nil {
return nil
}
if n.Val == p || n.Val == q {
return n
}
a := find(n.Left, p, q)
b := find(n.Right, p, q)
if a != nil && b != nil {
return n
}
if a != nil {
return a
}
return b
}find は、p と q が
計算量
- 時間は O(n) です。
どの 節にも 多くて 1 回ずつ行きます - 使う
記憶は O(h) です。 h は 木の 高さで、 再帰の 呼び出しが 深さの 分だけ積まれます。 1 本道の 木では O(n) に なります。 節が 500 以下なので、 Python の 再帰の 上限 (1000 段) には 届きません
よく
- 二分探索木の
決まりで 左右を選ぶ。 「 pとqが両方 自分より 小さければ 左へ」は 二分探索木でしか 使えません。 この 木は 値の 大きさと 位置が 関係ないので、 左右の 両方を探します - 片方が
祖先の 場合を落とす。 自分が pのとき、 さらに 下で qを探してから 決めようと すると、 例 2 のような 場合に 答えを 取り 違えやすくなります。 自分が pかqなら、その 時点で 自分を 返せば 正しく 決まります - 片方が
木に 無い 場合にも、 この 書き方を そのまま使う。 qが無いと、 pの節が そのまま 答えとして 返ってしまいます。 無いことがある 問題では、 2 つを 見つけた 数を 別に 数え、 2 つとも 見つかった ときだけ 答えにします - 節ではなく値で
比べる 前提を 確かめない。 値が 重なって よい 木なら、 値の 一致では 節を 決められません。 ここは 値が どれも 違うので、 値で 比べて 問題 ありません
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「根から 2 つの
値までの 道を 取り出して 比べる 書き方も ありますが、 木を 2 回た どります。 1 回に まとめる ため、 各節が 自分の 下で 見つけた 節を 返す再帰にします。 自分の 値が p か q なら 自分を 返し、 左右の 両方から 返ってきたら 自分が 答え、 片方だけなら それを 上へ渡します。 両方が 必ず木に あるという 条件に 頼っています。 時間は O(n)、 記憶は 木の 高さの 分です。」
書き終えたら、
「例 1 で
たどります。 根の 6 から 左の 15 へ 下ります。 15 の 左の 7 は q なので 7 が 返ります。 15 の 右の 11 では、 左の 2 が p なので 2 が 返り、 右の 13 からは 何も 返らないので、 11 は 2 を 返します。 15 は 左右の 両方から 返ってきたので、 自分の 15 を 返します。 根の 6 は 右の 3 から 何も 返らないので、 15 を そのまま 返し、 答えは 15 です。」