再帰で二分木を左右反転する｜コーディング面接問題

問題

二分木の根 root を受け取ります。すべての節で左の子と右の子を入れ替え、左右を鏡に映した形にした木の根を返す関数を書いてください。

各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
受け取った木をそのまま書き換えて返してかまいません
木が空のときは、空 (None、null、nil) を返します
節の数は 0 以上 100 以下、値はどれも -100 以上 100 以下です

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

入力と出力の例

例 1

根が 6、その下が 3 と 9、さらに下が 1、4、8、10 の木です。反転すると、各段が右から読んだ順になります。

入力

root = [6, 3, 9, 1, 4, 8, 10]

出力

[6, 9, 3, 10, 8, 4, 1]

例 2

右の子だけを持つ木です。反転すると、5 は左の子になります。

入力

root = [2, null, 5]

出力

[2, 5]

例 3

空の木です。

入力

root = []

出力

[]

面接での聞かれ方

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

「二分木を左右反転してください」
書き終えたあとに「再帰を使わずに書けますか？」と、待ち行列やスタックでの書き方を聞かれます
「元の木を壊さずに、新しい木を返すにはどうしますか？」と聞かれることもあります

書き換えてよいのか、新しい木を作るのかを最初に確かめておくと、記憶の話までまとめて答えられます。

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

まず考える手順

段 1

根だけを見ると、左の子と右の子を入れ替えれば済みそうに見えます。ただし、それだけでは孫より下の段の左右がそのままです。すべての節で入れ替える必要があります。

段 2

木は「根と、左の部分木と、右の部分木」でできています。左の部分木を反転した物と、右の部分木を反転した物を先に作り、根の左に右の結果を、右に左の結果を付ければ、木全体の反転になります。下の部分木の反転は、今書いている関数に任せられます。

段 3

止まる所は空の木です。空を反転しても空なので、そのまま返します。葉 (子の無い節) は、左右とも空を返されて入れ替えても形が変わらず、そのまま返ります。

解答

Python

def mirror_tree(root):
    if root is None:
        return None
    a = root.left
    b = root.right
    root.left = mirror_tree(b)
    root.right = mirror_tree(a)
    return root

JavaScript

function mirrorTree(root) {
  if (root === null) {
    return null;
  }
  const a = root.left;
  const b = root.right;
  root.left = mirrorTree(b);
  root.right = mirrorTree(a);
  return root;
}

Go

func mirrorTree(
	root *TreeNode,
) *TreeNode {
	if root == nil {
		return nil
	}
	a, b := root.Left, root.Right
	root.Left = mirrorTree(b)
	root.Right = mirrorTree(a)
	return root
}

元の左の子と右の子を、どちらも先に a と b に受けておくのが要です。root.left を書き換えたあとで root.left を読むと、元の左の子はもう残っていません。

計算量

時間は O(n) です。どの節にも 1 回ずつ行き、左右の付け替えを 1 回します
使う記憶は O(h) です。h は木の高さで、再帰の呼び出しが深さの分だけ積まれます。1 本道の木では O(n) になります

よくある間違い

書き換えてから、もう片方を読む。 変数に受けずに root.left = mirror_tree(root.right) のあとに root.right = mirror_tree(root.left) と書くと、2 行目の root.left はもう反転済みの右の部分木です。元の左の部分木は失われ、右の部分木が 2 回反転されて元に戻ったまま、左右の両方に付きます。両方の結果を先に変数へ受けます
根だけ入れ替える。根の左右を入れ替えただけでは、例 1 は [6, 9, 3, 8, 10, 1, 4] になり、下の段の順が逆になりません
空の木で止まる。 root.left を読む前に、root が空かを確かめます

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

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

再帰で二分木を左右反転する

問題