問題
二分木のroot を
- 道は、
親と 子を 結ぶ 辺を たどって、 同じ節を 2 回通らずに 1 つの 節から 別の 節へ 行く 経路です。 根を 通らなくてもかまいません - 長さは、
道が 通る 辺の数で 数えます (節の 数では ありません)。 節が 1 つだけの 木は 0 です - 各節は
val(値)、left(左の子)、 right(右の子) を 持ちます。 子が 無い ところは、 Python では None、JavaScript では null、Go では nilです。Go の 節は TreeNodeで、Val、Left、Rightと大文字で 始まります - 木が
空の ときは 0 を返します - 節の
数は 0 以上 500 以下、 値は どれも -100 以上 100 以下です
例では、null です。
入力と出力の例
例 1
根が 8、
入力
root = [8, 3, 10, 1, 6, null,
14, null, null, 4, 7]出力
5例 2
根の 5 には
入力
root = [5, 2, null, 1, 7, 0,
null, null, 9]出力
4例 3
節が 1 つだけの
入力
root = [4]出力
0面接での聞かれ方
面接では、
- 「二分木の
直径、 つまり いちばん長い 道の 長さを 返してください」 - 書き始める
前に 「長さは 辺の 数ですか、 節の 数ですか？」と 確かめると、 よい 印象になります - 書き終えた
あとに 「その道は 必ず根を 通りますか？」と 聞かれ、 例 2 のような 木で 確かめさせられます
辺で
アルゴリズムのチートシートの「再帰と木」に、この型の要点を表とコードでまとめています。
まず
段 1
まず、
段 2
ある
段 3
すべての
段 4
高さを
解答
Python
Python
def tree_diameter(root):
return walk(root)[1]
def walk(n):
if n is None:
return 0, 0
lh, lb = walk(n.left)
rh, rb = walk(n.right)
best = max(lb, rb, lh + rh)
return max(lh, rh) + 1, bestJavaScript
JavaScript
function treeDiameter(root) {
return walk(root)[1];
}
function walk(n) {
if (n === null) {
return [0, 0];
}
const [lh, lb] = walk(n.left);
const [rh, rb] = walk(
n.right
);
const best = Math.max(
lb, rb, lh + rh
);
const top = Math.max(lh, rh);
return [top + 1, best];
}Go
Go
func treeDiameter(
root *TreeNode,
) int {
_, best := walk(root)
return best
}
func walk(
n *TreeNode,
) (int, int) {
if n == nil {
return 0, 0
}
lh, lb := walk(n.Left)
rh, rb := walk(n.Right)
best := max(lb, rb, lh+rh)
h := max(lh, rh) + 1
return h, best
}walk は、max は 1.21 から
計算量
- 時間は O(n) です。
どの 節にも 1 回ずつ 行き、 子から 返った 値を 比べるだけです - 使う
記憶は O(h) です。 h は 木の 高さで、 再帰の 呼び出しが 深さの 分だけ積まれます。 1 本道の 木では O(n) に なります。 節が 500 以下なので、 Python の 再帰の 上限 (1000 段) には 届きません
よく
- 節の
数で答える。 道の 節の 数を 返すと、 答えが 1 大きくなります。 高さを 節の 数で 持つなら、 左と 右の 高さを 足した 値が そのまま 辺の 数に なり、 1 を 足しません - 根を
通る 道だけを見る。 根の 左の 高さと 右の 高さだけを 足すと、 例 2 では 3 に なり、 正しい 4 を 見落とします。 すべての 節で比べます - 高さを
節ごとに 数え直す。 各節で 高さを 別の 関数で 数え直すと、 1 本道の 木で O(n²) に なります。 高さと 最長の 道を 1 回の たどりで 一緒に返します - 最長の
道を 外の 変数に 持ち、 毎回の 呼び出しで 初めに戻す。 外に 置く 書き方なら、 関数の 最初で 1 回だけ 0 にします。 ここでは 返す値に 含めて、 外の 変数を 使っていません
解答を動かした版 Python 3.12.14Node.js 22.23.4Go 1.24.6確認日 2026年10月30日
面接での
書き始める
「どの
道にも 頂点に なる 節が 1 つ あり、 その節を 通る 最長の 道は 左の 高さと 右の 高さの 和です。 各節で 高さを 数え直すと O(n²) に なるので、 下から 1 回た どる 再帰で、 高さと そこまでの 最長の 道を 一緒に 返します。 長さは 辺の 数で 数えます。 時間は O(n)、 記憶は 木の 高さの 分です。」
書き終えたら、
「例 2 で
たどります。 0 と 9 は 高さ 1 です。 1 は 左の 高さ 1 で 高さ 2、 7 は 右の 高さ 1 で 高さ 2 です。 2 では 左右の 高さの 和が 4 に なり、 これが 最長です。 根の 5 は 左の 高さ 3、 右の 高さ 0 で 和は 3 なので、 答えは 4 のままです。」