深さ優先探索 (DFS) で二分木の深さを求める

木 (DFS と BFS)問題 37

二分木の根から一番遠い葉までの段の数を返す。左右の子の深さを先に求めて 1 を足す、深さ優先の再帰の練習です。

海外で定番の問題リスト 4 本のうち 4 本に入っています (Blind 75、NeetCode 150、Grind 75、LeetCode Top Interview 150)

問題

二分木の根 root を受け取ります。根から一番遠い葉までに通る段の数を返す関数を書いてください。根だけの木なら 1、空の木なら 0 です。

各節は、値 val、左の子 left、右の子 right を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
例では、木を上の段から順に、各段を左から右へ読んだ値の並びで書きます。子が無いところは null です。空の木は root = [] です
節の数は 0 以上 500 以下、値はどれも -1000 以上 1000 以下です

入力と出力の例

例 1

根 4 の下に 7 と 2、7 の右に 5、2 の左に 1 がある木です。一番深いのは 5 と 1 の段で、3 段です。

root = [4, 7, 2, null, 5, 1]

例 2

左の子だけが続く木です。片側に伸びても、数えるのは段の数です。

root = [1, 2, null, 3, null, 4]

例 3

空の木は 0 段です。

root = []

面接での聞かれ方

面接では、問題文がもっと短く渡されることが多いです。

「二分木の最大の深さを返してください」
書き終えたあとに「再帰を使わずに書けますか？」と続けて聞かれます
「木がとても深いと、何が困りますか？」と、再帰の深さを聞かれることもあります

深さを「段の数」で数えるのか「辺の数」で数えるのかで、答えが 1 つずれます。根だけなら 1 と数える、と先に確かめてから書くと安心です。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

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

再帰は、同じ形の小さい問題に分けて自分を呼ぶ書き方です。木の深さや、全部の組み合わせを数える問題で使います。

まず考える手順

段 1

まずは小さい木で考えます。空の木は 0 段、根だけの木は 1 段です。根に子が付くと、その子の下にどれだけ段が続くかで深さが決まります。

段 2

根から見た深さは、左の子の木の深さと右の子の木の深さの大きい方に、根の 1 段を足した数です。左右の子の木も同じ形の問題なので、同じ関数を子に向けて呼べば求まります。これが深さ優先の再帰です。

段 3

再帰の止まるところは、空の木で 0 を返す 1 か所だけです。葉では左右がどちらも空なので 0 と 0 の大きい方に 1 を足して 1 になり、特別に扱う必要はありません。

段 4

再帰を使わない書き方もあります。根だけを入れた並びから始め、いまの段の節を全部取り出して、その子を次の段の並びに入れます。これを並びが空になるまで繰り返し、繰り返した回数を数えると段の数になります。段ごとに数えるので、幅優先と呼ばれます。

解答

Python

def tree_depth(root):
    if root is None:
        return 0
    lh = tree_depth(root.left)
    rh = tree_depth(root.right)
    return max(lh, rh) + 1

JavaScript

function treeDepth(root) {
  if (root === null) {
    return 0;
  }
  const { left, right } = root;
  const lh = treeDepth(left);
  const rh = treeDepth(right);
  return Math.max(lh, rh) + 1;
}

Go

func treeDepth(
	root *TreeNode,
) int {
	if root == nil {
		return 0
	}
	lh := treeDepth(root.Left)
	rh := treeDepth(root.Right)
	return max(lh, rh) + 1
}

空の木を 0 段と決めてあるので、葉も、子が片方だけの節も、同じ 1 行で扱えます。

計算量

時間は O(n) です。どの節も 1 回ずつ訪れます
使う記憶は O(h) です。h は木の深さで、再帰の呼び出しが h 段まで積み重なります。例 2 のように片側に伸びた木では、h は n と同じになります
Python は既定で、呼び出しが約 1000 段重なると RecursionError で止まります。節の数を 500 までにしているのはこのためです。節が何千もある偏った木が来るなら、段 4 の幅優先の書き方に替えます
段 4 の幅優先の書き方も、時間は O(n) です。記憶は 1 つの段に並ぶ節の数だけ使います

よくある間違い

空の木を考えない。先に root.left を読むと、空の木で落ちます。空なら 0 を返す行を一番先に置きます
葉で止めようとして子が片方の節で間違える。「左右とも空なら 1」だけを止まるところにすると、子が片方だけの節で空の側を読みに行って落ちます。空の木を 0 とする 1 か所にまとめると安全です
大きい方でなく小さい方を取る。深さは一番遠い葉までなので、左右の大きい方を取ります。小さい方を取ると、一番近い葉までの段の数という別の答えになります

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

main.py

def tree_depth(root: TreeNode | None) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # root の節は val、left、right を持ちます。空きは None です
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
# build_tree は、例と同じ並びから木を組みます
print(tree_depth(build_tree([4, 7, 2, None, 5, 1])))

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