【Python】二分木で偶数値のみからなる最長パスを求めるアルゴリズムと実装

問題概要

二分木が与えられたとき、木の中の任意の2つのノードをつなぐ経路のうち、偶数の値のみで構成される最長のパスの長さを見つけることを考えます。

例えば、次のような二分木が入力として与えられた場合を考えてみましょう。

この場合、最長のパスは [10, 2, 4, 8, 6] となるため、出力は 5 になります。

解法のアプローチ

この問題は、再帰的な深さ優先探索（DFS）を使うことで効率的に解くことができます。各ノードについて「左部分木から伸びる偶数パスの長さ」と「右部分木から伸びる偶数パスの長さ」を求め、それらを組み合わせて全体の答えを更新していくのがポイントです。

具体的には、以下の手順で処理を進めます。

• 答えを格納する変数 ans を 0 で初期化します。
• 関数 find(node) を定義します。
• node が null（None）の場合は (-1, -1) を返します。
• leftCnt := 左の子に対する find() の戻り値の最大値 + 1
• rightCnt := 右の子に対する find() の戻り値の最大値 + 1
• ノードの値が偶数の場合：
  • ans := max(ans, leftCnt + rightCnt + 1) で答えを更新
  • (leftCnt, rightCnt) を返す
• ノードの値が奇数の場合：
  • ans := max(ans, leftCnt, rightCnt) で答えを更新
  • (-1, -1) を返す（ここでパスが途切れるため）
• メイン処理では find(root) を呼び出し、最後に ans を返します。

なぜ -1 を返すのか？

奇数のノードに到達した時点で、偶数値のみのパスは途切れてしまいます。-1 を返すことで、親ノード側でのパス長の計算時にこの途切れを正しく反映できる仕組みになっています。また、戻り値に +1 しているのは、子ノードから現在のノードへ向かう1本の辺をカウントするためです。

実装例

それでは、実際のコードを見てみましょう。

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def solve(self, root):
        ans = 0
        def find(node):
            nonlocal ans
            if not node:
                return -1, -1
            leftCnt = max(find(node.left)) + 1
            rightCnt = max(find(node.right)) + 1
            if node.val % 2 == 0:
                ans = max(ans, leftCnt + rightCnt + 1)
                return leftCnt, rightCnt
            else:
                ans = max(ans, max(leftCnt, rightCnt))
                return -1, -1
        find(root)
        return ans

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)
print(ob.solve(root))

入力

root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

出力

5

計算量について

• 時間計算量： O(N) — 各ノードをちょうど1回ずつ訪問するため、ノード数 N に対して線形時間で処理できます。
• 空間計算量： O(H) — 再帰呼び出しのスタックの深さは木の高さ H に依存します。平衡な二分木であれば O(log N)、最悪ケース（連結リスト状の木）では O(N) となります。

まとめ

本記事では、二分木において偶数の値のみで構成される最長パスの長さを求める問題を、再帰的なDFSを用いて解く方法を解説しました。各ノードで左右の部分木からのパス長を管理し、奇数ノードでパスをリセットするというシンプルな発想が鍵となります。木構造のパスに関する問題では頻出のテクニックなので、ぜひマスターしておきましょう。