深さ優先探索で根からの道でいちばん大きい値を持ち回り、二分木のよい節を数える

木 (DFS と BFS)問題 93

根からその節までの道に、その節より大きい値が 1 つも無い節を「よい節」と呼び、その数を返します。上から下へ、ここまでの最大値を引数で渡していく深さ優先探索の練習です。

海外で定番の問題リスト 4 本には入っていません

問題

二分木の根 root を受け取ります。根からある節までの道 (その節自身を含む) に、その節の値より大きい値が 1 つも無いとき、その節を「よい節」と呼びます。よい節の数を返す関数を書いてください。

道の途中に、その節と同じ値があってもかまいません。大きい値が無ければよい節です
根は、道に自分しかいないので、いつもよい節です
各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
節の数は 1 以上 500 以下、値はどれも -10000 以上 10000 以下です

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

入力と出力の例

例 1

山道の分かれ道ごとの標高を木にした物です。登ってきた道のどこよりも高い (または同じ高さの) 地点を数えます。根が 5、その下が 3 と 8、3 の左に 6、8 の下に 2 と 9 です。根の 5、8、9、それに左下の 6 (道は 5、3、6 で、6 より大きい値が無い) の 4 つがよい節です。

root = [5, 3, 8, 6, null, 2, 9]

例 2

根の 4 の左に 4、その左に 1、右に 7 があります。左の 4 は道の根と同じ値で、大きい値は無いのでよい節です。1 は、道に 4 があるのでよい節ではありません。ほかの 3 つはよい節です。

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

例 3

節が 1 つだけの木です。根はいつもよい節です。

root = [-5]

面接での聞かれ方

木の深さ優先探索で「上から下へ情報を渡す」型として、ミドルの面接で出ます。

「根からの道に自分より大きい値が無い節を数えてください」
木の深さを求める問題のように「下から上へ値を返す」再帰と比べて、「上から下へ引数で渡す」再帰の書き方を見るために出されます
「再帰を使わずに書けますか？」と聞かれることがあります。節と、そこまでの最大値の組をスタックに積めば同じことができます

ミドルの問題なので、道ごとに道の値を全部持たず、「ここまでの最大値」1 つだけを渡せばよいと気づけるかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、根からの道の値を並びで持ち回り、各節で並びの中に自分より大きい値があるかを調べる書き方を考えます。動きますが、節ごとに道の長さの分だけ調べるので、1 本道の木では O(n²) になります。

段 2

ある節がよい節かどうかに要るのは、道の値の全部ではなく、道でいちばん大きい値だけです。それが自分以下なら、自分より大きい値は 1 つも無いからです。

段 3

そこで、深さ優先探索で節を訪ねるとき、「根からここに来るまでの最大値」を引数で渡します。自分の値がそれ以上ならよい節で 1 と数え、子へは、最大値と自分の値の大きい方を渡します。

段 4

根は、最大値を根自身の値として始めれば、よい節と数えられます。空の節は 0 を返し、各節は自分の 1 か 0 と、左右の子の数を足して返します。

解答

Python

def good_nodes(root):
    def walk(n, best):
        if n is None:
            return 0
        ok = int(n.val >= best)
        top = max(best, n.val)
        a = walk(n.left, top)
        b = walk(n.right, top)
        return ok + a + b
    return walk(root, root.val)

JavaScript

function goodNodes(root) {
  const walk = (node, best) => {
    if (node === null) {
      return 0;
    }
    const good =
      node.val >= best ? 1 : 0;
    const top =
      Math.max(best, node.val);
    return good
      + walk(node.left, top)
      + walk(node.right, top);
  };
  return walk(root, root.val);
}

Go

func goodNodes(
	root *TreeNode,
) int {
	return walkGood(
		root, root.Val)
}

func walkGood(
	n *TreeNode, best int,
) int {
	if n == nil {
		return 0
	}
	good := 0
	if n.Val >= best {
		good = 1
	}
	best = max(best, n.Val)
	return good +
		walkGood(n.Left, best) +
		walkGood(n.Right, best)
}

best は、根からこの節の親までの道でいちばん大きい値です。子へ渡すときは、自分の値も含めた最大値にします。

計算量

時間は O(n) です。どの節にも 1 回ずつ行き、比べるのは 1 回だけです
使う記憶は O(h) です。h は木の高さで、再帰の呼び出しが深さの分だけ積まれます。1 本道の木では O(n) になります。節が 500 以下なので、Python の再帰の上限 (1000 段) には届きません

よくある間違い

> で比べる。 道に同じ値があってもよい節です。例 2 の左の 4 は、道の根も 4 ですが、よい節です。>= で比べます
親の値とだけ比べる。親より大きくても、もっと上により大きい値があればよい節ではありません。渡すのは、道全体の最大値です
最大値を外の変数に持ち、戻るときに戻し忘れる。 左の枝で上げた最大値が、右の枝にまで残ります。引数で渡せば、枝ごとに別の値になります
最初の最大値を 0 にする。値は負の数もあるので、例 3 の -5 が 0 より小さく、よい節と数えられません。根の値か、いちばん小さい数から始めます

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def good_nodes(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(good_nodes(build_tree([5, 3, 8, 6, None, 2, 9])))

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