再帰で並びから高さのそろった二分探索木を作る｜コーディング面接問題

問題

小さい順に並んだ整数の並び nums を受け取ります。この数を全部 1 つずつ使って二分探索木を作り、その根を返す関数を書いてください。どの節でも、左の部分木と右の部分木の高さの差が 1 以下になるようにします。

二分探索木は、どの節でも、左の部分木の値は全部その節より小さく、右の部分木の値は全部その節より大きい木です
作り方は 1 通りに決めます。いま使う範囲の左端の番号と右端の番号を足して 2 で割り、端数を切り捨てた番号の値を根にします。その左側の範囲から左の部分木を、右側の範囲から右の部分木を、同じ決め方で作ります
新しい節は、Python では TreeNode(値)、JavaScript では new TreeNode(値)、Go では &TreeNode{} で作れます。どれも val (値)、left (左の子)、right (右の子) を持ち、子は最初は空です。Go では Val、Left、Right と大文字で始まります
数の個数は 1 以上 500 以下、値はどれも -1000 以上 1000 以下で、同じ値はありません

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

入力と出力の例

例 1

7 つの数です。まん中の 11 が根になり、左の 3 つと右の 3 つからそれぞれ同じ形の木ができます。

入力

nums = [2, 5, 8, 11, 14, 17, 20]

出力

[11, 5, 17, 2, 8, 14, 20]

例 2

5 つの数です。左の範囲は 2 つしかないので、切り捨てで左寄りの -10 が根になり、-3 はその右の子になります。右の範囲の 5 と 9 も同じです。

入力

nums = [-10, -3, 0, 5, 9]

出力

[0, -10, 5, null, -3, null, 9]

例 3

2 つだけの数です。まん中の候補は 2 つありますが、切り捨てで左の 3 が根になり、6 はその右の子です。

入力

nums = [3, 6]

出力

[3, null, 6]

面接での聞かれ方

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

「小さい順の並びから、高さの釣り合った二分探索木を作ってください」
書き終えたあとに「なぜまん中を根にすると高さがそろうのですか？」と理由を聞かれます
「並びではなく、小さい順の連結リストで渡されたらどうしますか？」と形を変えて聞かれることもあります

まん中が 2 つあるときにどちらを根にするかで答えの木が変わるので、最初に決め方を口に出しておきます。

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

まず考える手順

段 1

まず、二分探索木の決まりを思い出します。根より小さい値は全部左、大きい値は全部右です。並びは小さい順なので、どれか 1 つを根に選ぶと、その左側の数が左の部分木、右側の数が右の部分木にそのまま分かれます。

段 2

次に、どれを根にすれば高さがそろうかを考えます。端の数を根にすると、片側に全部が寄って 1 本道になります。まん中を根にすれば、左右に残る数の差が 1 以下になり、高さもそろいます。

段 3

左右の部分木も、同じ問題の小さい版です。そこで「範囲の左端と右端の番号を受け取り、その範囲から木を作って根を返す」関数を書き、自分自身を左右の範囲で呼びます。左端が右端を越えたら範囲は空なので、空の木を返します。

段 4

範囲を切り出した新しい並びを渡すと、そのたびに写しが作られます。並びはそのまま共有し、左端と右端の番号だけを渡すと、写しの手間がかかりません。

解答

Python

def sorted_to_bst(nums):
    last = len(nums) - 1
    return grow(nums, 0, last)


def grow(nums, lo, hi):
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = TreeNode(nums[mid])
    node.left = grow(
        nums, lo, mid - 1
    )
    node.right = grow(
        nums, mid + 1, hi
    )
    return node

JavaScript

function sortedToBst(nums) {
  const last = nums.length - 1;
  return grow(nums, 0, last);
}

function grow(nums, lo, hi) {
  if (lo > hi) {
    return null;
  }
  const mid = Math.floor(
    (lo + hi) / 2
  );
  const node = new TreeNode(
    nums[mid]
  );
  node.left = grow(
    nums, lo, mid - 1
  );
  node.right = grow(
    nums, mid + 1, hi
  );
  return node;
}

Go

func sortedToBst(
	nums []int,
) *TreeNode {
	last := len(nums) - 1
	return grow(nums, 0, last)
}

func grow(
	nums []int, lo, hi int,
) *TreeNode {
	if lo > hi {
		return nil
	}
	mid := (lo + hi) / 2
	v := nums[mid]
	node := &TreeNode{Val: v}
	node.Left = grow(
		nums, lo, mid-1,
	)
	node.Right = grow(
		nums, mid+1, hi,
	)
	return node
}

番号は 0 以上なので、Go の整数の割り算と JavaScript の Math.floor は、どちらも Python の // と同じ切り捨てになります。

計算量

時間は O(n) です。どの数からも節を 1 つ作るだけで、範囲を切り出す写しは作りません
使う記憶は、返す木の n 個の節のほかに O(log n) です。まん中で半分ずつに分けるので、再帰の深さは木の高さ、つまり log n 程度で止まります

よくある間違い

範囲の切り出しで写しを作る。範囲を切り出した新しい並びを毎回渡すと、写しの分だけ時間と記憶が増え、全体で O(n log n) になります。番号だけを渡します
右端の扱いが混ざる。右端を「含む」番号にするか「含まない」番号にするかを途中で取り違えると、数が 1 つ抜けたり、同じ数を 2 回使ったりします。ここでは両端を含む形にそろえ、空の判定は lo > hi にします
まん中の決め方を決めずに書く。例 3 のように数が偶数個の範囲では、まん中の候補が 2 つあります。左寄りか右寄りかで答えの木が変わるので、問題の決め方 (切り捨てで左寄り) に合わせます

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

main.py

def sorted_to_bst(nums):
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(sorted_to_bst([2, 5, 8, 11, 14, 17, 20]))

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

再帰で並びから高さのそろった二分探索木を作る

問題