再帰で 2 本の二分木が同じか確かめる｜コーディング面接問題

問題

二分木の根 root1 と root2 を受け取ります。2 本の木が、形も、同じ位置にある値もすべて同じなら真、1 か所でも違えば偽を返す関数を書いてください。

各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
空の木どうしは同じと見ます
節の数はそれぞれ 0 以上 100 以下、値はどれも -10000 以上 10000 以下です

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

入力と出力の例

例 1

どちらも、根が 3、その下が 9 と 4、9 の左に 1 がある木です。

入力

root1 = [3, 9, 4, 1]
root2 = [3, 9, 4, 1]

出力

true

例 2

値の並びは同じに見えますが、root1 の 6 は左の子、root2 の 6 は右の子です。形が違うので偽です。

入力

root1 = [2, 6]
root2 = [2, null, 6]

出力

false

例 3

形は同じですが、右下の値が 5 と 8 で違います。

入力

root1 = [7, 5, 5]
root2 = [7, 5, 8]

出力

false

面接での聞かれ方

面接では、短く次のように渡されることが多いです。

「二分木が 2 つあります。同じ木かどうかを判定してください」
書き終えたあとに「左右を鏡に映した形と同じか、に変えられますか？」と聞かれることがあります
「再帰を使わずに書けますか？」と、待ち行列での書き方を聞かれることもあります

木の問題では、「片方だけ空」の場合をどう扱うかを最初に口に出しておくと、書き落としが減ります。

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

まず考える手順

段 1

まず、両方の木を段の順の並びに直してから比べる書き方が浮かびます。ただし、並びに直すときに空きを null で残さないと、例 2 のように形の違いが消えてしまいます。並びを作る手間と記憶もかかります。

段 2

木は「根と、左の部分木と、右の部分木」でできています。2 本の木が同じなのは、根の値が同じで、左どうしが同じで、右どうしも同じときです。左どうし、右どうしの比べは、今書いている関数そのものに任せられます。

段 3

再帰の止まる所を決めます。両方とも空なら同じです。片方だけ空なら違います。この 2 つを先に片付けてから値を比べれば、空の節の val を読むことはありません。

解答

Python

def is_same_tree(root1, root2):
    if root1 is None:
        return root2 is None
    if root2 is None:
        return False
    if root1.val != root2.val:
        return False
    a = root1.left
    b = root2.left
    if not is_same_tree(a, b):
        return False
    a = root1.right
    b = root2.right
    return is_same_tree(a, b)

JavaScript

function isSameTree(
  root1, root2
) {
  if (root1 === null) {
    return root2 === null;
  }
  if (root2 === null) {
    return false;
  }
  if (root1.val !== root2.val) {
    return false;
  }
  const l1 = root1.left;
  const l2 = root2.left;
  if (!isSameTree(l1, l2)) {
    return false;
  }
  const r1 = root1.right;
  const r2 = root2.right;
  return isSameTree(r1, r2);
}

Go

func isSameTree(
	root1, root2 *TreeNode,
) bool {
	if root1 == nil {
		return root2 == nil
	}
	if root2 == nil {
		return false
	}
	if root1.Val != root2.Val {
		return false
	}
	a, b := root1.Left, root2.Left
	if !isSameTree(a, b) {
		return false
	}
	a = root1.Right
	b = root2.Right
	return isSameTree(a, b)
}

3 言語とも、root1 が空なら「root2 も空か」をそのまま返し、そのあと root2 だけが空の場合を偽で返します。ここまでで、どちらの val を読んでも止まらないことが決まります。

計算量

時間は O(n) です。n は節の少ない方の木の節の数で、違いが見つかった所で止まります。同じ木なら全部の節を 1 回ずつ比べます
使う記憶は O(h) です。h は木の高さで、再帰の呼び出しが深さの分だけ積まれます。1 本道の木では O(n) になります

よくある間違い

値だけを比べて、空を先に見ない。 root1.val を先に読むと、片方が空のときに止まります。空の判定を値の比べより前に置きます
空きを落として並びにしてから比べる。例 2 の 2 本は、空きを書かずに読むとどちらも [2, 6] になり、同じと判定してしまいます
鏡の形と取り違える。左と右を入れ替えて比べるのは「左右対称か」の問題です。この問題は、左どうし、右どうしを比べます

解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日

def is_same_tree(root1, root2): # root の節は val、left、right を持ちます。空きは None です # ここに書きます pass # 「実行」を押すと、この行の結果が出ます # build_tree は、例と同じ並びから木を組みます print(is_same_tree(build_tree([3, 9, 4, 1]), build_tree([3, 9, 4, 1])))

再帰で 2 本の二分木が同じか確かめる

問題