再帰で二分木の中に別の木と同じ部分木があるか確かめる

大きい二分木のどこかの節から下が、小さい二分木とそっくり同じかを返します。どの節を根にするかを探す再帰と、2 本の木が同じかを比べる再帰を組み合わせる練習です。

海外で定番の問題リスト 4 本には入っていません

問題

2 本の二分木の根 root1 と root2 を受け取ります。root1 の木のどこかの節について、その節とその下の子孫を全部合わせた部分木が、root2 の木と形も値もそっくり同じなら true、そうでなければ false を返す関数を書いてください。

部分木は、ある節から下を葉まで全部含めた物です。途中で切った形は部分木ではありません
root1 の木そのものも、root1 の部分木の 1 つです
各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
root1 の節の数は 1 以上 2000 以下、root2 の節の数は 1 以上 1000 以下、値はどれも -10000 以上 10000 以下です

例では、木を上の段から左の順に読んだ値の並びで書きます。子が無いところは null です。

入力と出力の例

例 1

根が 8、その下が 6 と 9、6 の下に 2 と 7 の木です。root1 の 6 の節から下は、6 の左に 2、右に 7 で、root2 とそっくり同じです。

root1 = [8, 6, 9, 2, 7] root2 = [6, 2, 7]

true

例 2

root1 の 6 の節から下は、7 の左にさらに 5 が付いています。葉まで全部比べると root2 と違うので、部分木ではありません。

root1 = [8, 6, 9, 2, 7, null, null, null, null, 5] root2 = [6, 2, 7]

false

例 3

値が同じでも、左と右が違えば同じ形ではありません。root1 の 2 の節から下は 2 の左に 7 ですが、root2 は 2 の右に 7 です。

root1 = [1, 2, 3, 7] root2 = [2, null, 7]

false

面接での聞かれ方

木の再帰を 2 つ組み合わせる問題として、ジュニアの面接で出ます。

「この木の中に、もう 1 本の木と同じ部分木があるかを調べてください」
2 本の木が同じかを調べる問題 (この一覧の same-tree) の続きとして出されることがよくあります
書き終えたあとに「もっと速くできますか？」と聞かれることがあります。木を区切りの付いた文字列に直して文字列の中を探す書き方や、部分木ごとに指紋 (ハッシュ) を付ける書き方で、O(m + n) にできます

ジュニアの問題なので、「どこを根にするか」と「同じか」の 2 つの関数に分けて考えられるかが見られます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

まず、2 本の木がそっくり同じかを調べる関数 same(a, b) を用意します。両方とも空なら同じ、片方だけ空なら違う、値が違えば違う、どれでもなければ左どうしと右どうしを同じ関数で比べます。

段 2

root1 の部分木の根になれるのは、root1 のどの節でもかまいません。そこで、root1 の節を 1 つずつ根に見立てて、same(その節, root2) を試します。

段 3

節を順に試すのも再帰で書けます。今の節で same が成り立てば true、そうでなければ左の子の下と右の子の下で同じことを試し、どちらかで見つかれば true です。空の節まで来たら、そこには部分木が無いので false です。

段 4

例 2 のように値の並びの途中まで同じでも、same は葉の下の空まで比べるので、余分な節があれば違うと分かります。

解答

Python

def same(a, b):
    if a is None or b is None:
        return a is b
    if a.val != b.val:
        return False
    return (same(a.left, b.left)
            and same(a.right,
                     b.right))


def subtree_check(root1, root2):
    if root1 is None:
        return False
    if same(root1, root2):
        return True
    return (subtree_check(
        root1.left, root2)
        or subtree_check(
            root1.right, root2))

JavaScript

function same(a, b) {
  if (a === null
    || b === null) {
    return a === b;
  }
  return a.val === b.val
    && same(a.left, b.left)
    && same(a.right, b.right);
}

function subtreeCheck(
  root1, root2
) {
  if (root1 === null) {
    return false;
  }
  if (same(root1, root2)) {
    return true;
  }
  return subtreeCheck(
    root1.left, root2
  ) || subtreeCheck(
    root1.right, root2
  );
}

Go

func same(a, b *TreeNode) bool {
	if a == nil || b == nil {
		return a == b
	}
	return a.Val == b.Val &&
		same(a.Left, b.Left) &&
		same(a.Right, b.Right)
}

func subtreeCheck(
	root1, root2 *TreeNode,
) bool {
	if root1 == nil {
		return false
	}
	if same(root1, root2) {
		return true
	}
	return subtreeCheck(
		root1.Left, root2,
	) || subtreeCheck(
		root1.Right, root2,
	)
}

same の最初の行は、両方とも空なら true、片方だけ空なら false を 1 行で返します。

計算量

時間は O(m × n) です。m は root1 の節の数、n は root2 の節の数で、root1 の節ごとに same が多くて n 個の節を比べます
使う記憶は O(h) です。h は root1 の高さで、再帰の呼び出しが深さの分だけ積まれます。1 本道の木では O(m) になります

よくある間違い

根の値が同じ節だけを試し、見つかったら終える。値が同じ節は何個もあることがあります。1 つ目で same が成り立たなくても、ほかの節で成り立つことがあるので、全部の節を試します
途中まで同じなら同じと見る。 root2 の葉まで比べて終えると、例 2 の余分な 5 を見落とします。same は両方の空まで比べます
値の並びを文字列にして探す。空の子の印や区切りを付けずに文字列にすると、12 と 2 が「2」で当たったり、形の違う木が同じ文字列になったりします。文字列で探すなら、値の前後に区切りを付け、空の子も印で書きます
左と右のどちらかで見つかったのに、もう片方の結果で上書きする。 or (||) でつなぎ、どちらかで見つかれば true にします

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def subtree_check(root1: TreeNode | None, root2: TreeNode | None) -> bool:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # root の節は val、left、right を持ちます。空きは None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_tree は、例と同じ並びから木を組みます
print(subtree_check(build_tree([8, 6, 9, 2, 7]), build_tree([6, 2, 7])))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します