問題
二分木のroot を
- 高さは、
その 部分木の 根から いちばん深い 節までの 節の 数です。 空の 部分木の 高さは 0 です - 根だけでなく、
すべての 節で 差を 確かめます - 各節は
val(値)、left(左の子)、 right(右の子) を 持ちます。 子が 無い ところは、 Python では None、JavaScript では null、Go では nilです。Go の 節は TreeNodeで、Val、Left、Rightと大文字で 始まります - 木が
空の ときは 真を返します - 節の
数は 0 以上 500 以下、 値は どれも -100 以上 100 以下です
例では、null です。
入力と出力の例
例 1
根が 7、
入力
root = [7, 3, 9, null, 5, 8]出力
true例 2
根の 6 では、
入力
root = [6, 4, 8, 2, null, null,
9, 1]出力
false例 3
空の
入力
root = []出力
true面接での聞かれ方
面接では、
- 「この
二分木の 高さが 釣り合っているかを 判定してください」 - 根だけを
比べる 書き方を 出すと、 例 2 のような 木を 示して 「これは どうなりますか？」と 聞かれます - 書き終えた
あとに 「高さを 何回数えていますか？ 1 回の たどりに できますか？」と、 計算量を 詰めるよう 聞かれます
「釣り合い」の
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
まず浮かぶのは、
段 2
見方を
段 3
差が 2 以上の
段 4
左の
解答
Python
Python
def is_balanced(root):
return height(root) >= 0
def height(n):
if n is None:
return 0
lh = height(n.left)
if lh < 0:
return -1
rh = height(n.right)
if rh < 0:
return -1
if abs(lh - rh) > 1:
return -1
return max(lh, rh) + 1JavaScript
JavaScript
function isBalanced(root) {
return height(root) >= 0;
}
function height(n) {
if (n === null) {
return 0;
}
const lh = height(n.left);
if (lh < 0) {
return -1;
}
const rh = height(n.right);
if (rh < 0) {
return -1;
}
if (Math.abs(lh - rh) > 1) {
return -1;
}
return Math.max(lh, rh) + 1;
}Go
Go
func isBalanced(
root *TreeNode,
) bool {
return height(root) >= 0
}
func height(n *TreeNode) int {
if n == nil {
return 0
}
lh := height(n.Left)
if lh < 0 {
return -1
}
rh := height(n.Right)
if rh < 0 {
return -1
}
if lh-rh > 1 || rh-lh > 1 {
return -1
}
return max(lh, rh) + 1
}height は、
計算量
- 時間は O(n) です。
どの 節にも 多くて 1 回ずつ 行き、 高さの 比べを 1 回します - 使う
記憶は O(h) です。 h は 木の 高さで、 再帰の 呼び出しが 深さの 分だけ積まれます。 1 本道の 木では O(n) に なります。 節が 500 以下なので、 Python の 再帰の 上限 (1000 段) には 届きません
よく
- 根だけで比べる。
根の 左右の 高さだけを 比べると、 例 2 のように 下の 節で 崩れている 木を 真と 答えてしまいます。 すべての 節で 差を 確かめます - 高さを
節ごとに 数え直す。 高さの 関数と 判定の 関数を 別々に して、 各節で 高さを 数え直すと、 1 本道に 近い木で O(n²) に なります。 高さと 判定を 1 回の たどりに まとめます - 崩れの
印を 受け取った あとも 計算を続ける。 子から -1 が 返ったのに、 そのまま max(lh, rh) + 1を計算すると、 -1 が 0 や 1 に 化けて 崩れが 消える ことがあります。 -1 を 見たら すぐ -1 を返します - 最小の
深さと 最大の 深さの 差で 判定する。 「いちばん浅い 葉と いちばん深い 葉の 差が 1 以下」は 別の 決まりです。 各節での 左右の 差で見ます
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「各節で
左右の 高さを 数え直すと O(n²) に なるので、 下から 1 回た どる 再帰で 高さを 返し、 その ついでに 差を 確かめます。 差が 2 以上の 節を 見つけたら、 高さとして あり得ない -1 を 印として 返し、 親は それを 見たら そのまま -1 を 返します。 根の 結果が -1 でなければ 真です。 時間は O(n)、 記憶は 木の 高さの 分です。」
書き終えたら、
「例 2 で
たどります。 1 は 高さ 1、 2 は 左が 1 で 右が 0 なので 高さ 2 です。 4 は 左が 2 で 右が 0、 差が 2 なので -1 を 返します。 根の 6 は 左から -1 を 受け取ったので、 右の 8 を 見ずに -1 を 返し、 答えは 偽です。」