再帰で二分木の道の値の合計がいちばん大きくなる所を探す

木 (DFS と BFS)問題 94

二分木の中で、節をつないだ道の値の合計のうち、いちばん大きい値を返します。負の値の枝を切り捨てながら、下へ伸ばせる片道の和を返し、ついでに曲がる道を比べる再帰の練習です。

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

問題

二分木の根 root を受け取ります。木の中の道のうち、道が通る節の値の合計がいちばん大きい物の、その合計を返す関数を書いてください。

道は、親と子を結ぶ辺をたどって、同じ節を 2 回通らずにつないだ節の列です。節が 1 つだけでも道です
道は根を通らなくてもかまいません。ある節で左の枝から上がってきて右の枝へ降りる、という曲がり方は 1 回だけできます
値には負の数もあります。全部が負なら、答えはいちばん大きい 1 つの節の値です
各節は val (値)、left (左の子)、right (右の子) を持ちます。子が無いところは、Python では None、JavaScript では null、Go では nil です。Go の節は TreeNode で、Val、Left、Right と大文字で始まります
節の数は 1 以上 500 以下、値はどれも -1000 以上 1000 以下です

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

入力と出力の例

例 1

根が 2、その下が 6 と -4、6 の下に 5 と 1、-4 の右に 9 です。5 から 6、2 と上がって、-4、9 と下る道の合計は 5 + 6 + 2 − 4 + 9 = 18 で、これがいちばん大きくなります。

root = [2, 6, -4, 5, 1, null, 9]

例 2

根の -6 を通ると損をします。根を通る道は、いちばん大きくても 4 − 6 + 12 + 10 = 20 です。根を通らず、右の 12 で 10 から 12、3 と曲がる道の 25 がいちばん大きくなります。

root = [-6, 4, 12, null, null, 10, 3]

例 3

全部の値が負の木です。どの道も、節を足すほど小さくなるので、いちばん大きい 1 つの節の -2 が答えです。

root = [-3, -2, -5]

-2

面接での聞かれ方

木の再帰の難しい問題として、シニアの面接でよく出ます。

「二分木の道の合計の最大を求めてください。道は根を通らなくてもよく、値には負の数もあります」
二分木の直径を求める問題 (この一覧の tree-diameter) と同じ形で、辺の数の代わりに値を足し、負の値を捨てる判断が加わった物です
「どの道が最大か、道そのものも返せますか？」と続けて聞かれることがあります

シニアの問題なので、「親へ返す値」と「その節で比べる値」が違うことを、言葉で説明できるかが見られます。

ヒント

まだ開いていません

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

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

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

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

まず考える手順

段 1

まずは素直に、全部の節の組を道の両端に選び、その道の合計を数える書き方を考えます。組が O(n²) あり、それぞれの道をたどるので、とても遅くなります。

段 2

どの道にも、いちばん上の節 (曲がる所) が 1 つあります。そこで、節ごとに「この節をいちばん上にした道の最大」を求め、全部の節で比べれば答えです。この節をいちばん上にした道は、この節の値に、左の子から下へ伸びる片道の最大と、右の子から下へ伸びる片道の最大を足した物です。

段 3

「子から下へ伸びる片道の最大」は、再帰で子から返してもらいます。片道は曲がれないので、自分の値に、左右の片道の大きい方だけを足して親へ返します。

段 4

片道の和が負なら、その枝は使わない方が得です。子から返った値は 0 と比べて大きい方を使います。こうすると、全部が負の木でも、節 1 つだけの道が正しく比べられます。比べた最大は、関数の外の変数か返り値で持ちます。

解答

Python

def max_path_sum(root):
    best = root.val

    def down(n):
        nonlocal best
        if n is None:
            return 0
        l = down(n.left)
        r = down(n.right)
        l = max(l, 0)
        r = max(r, 0)
        here = n.val + l + r
        best = max(best, here)
        return n.val + max(l, r)

    down(root)
    return best

JavaScript

function maxPathSum(root) {
  let best = root.val;
  const down = (n) => {
    if (n === null) {
      return 0;
    }
    const l = Math.max(
      down(n.left), 0);
    const r = Math.max(
      down(n.right), 0);
    best = Math.max(
      best, n.val + l + r);
    return n.val
      + Math.max(l, r);
  };
  down(root);
  return best;
}

Go

func maxPathSum(
	root *TreeNode,
) int {
	best := root.Val
	var down func(*TreeNode) int
	down = func(n *TreeNode) int {
		if n == nil {
			return 0
		}
		l := max(down(n.Left), 0)
		r := max(down(n.Right), 0)
		best = max(best, n.Val+l+r)
		return n.Val + max(l, r)
	}
	down(root)
	return best
}

down が返すのは、その節から下へ伸びる片道の最大 (親へつなげる形) です。best を比べるのは、その節で曲がる道の和です。

計算量

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

よくある間違い

親へ左右の両方を足した値を返す。両方を足した道は、その節で曲がっています。親へつなぐと 2 回曲がる形になり、道ではなくなります。親へ返すのは片方だけです
負の枝を捨てない。子からの片道が負のときに足すと、その分だけ合計が下がります。例 3 で、根の -3 から見て左の -2 を足すと -5 になり、正しくは足さずに比べます。0 と比べて大きい方を使います
best を 0 から始める。 全部が負の木では答えが負なので、例 3 で 0 を返してしまいます。根の値か、いちばん小さい数から始めます
根を通る道だけを見る。例 2 のように、根を通らない道が最大のことがあります。すべての節で、その節で曲がる道を比べます

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

main.py

def max_path_sum(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(max_path_sum(build_tree([2, 6, -4, 5, 1, None, 9])))

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