Pythonで二分木の最小共通祖先（LCA）を求めるアルゴリズムと実装例

はじめに

二分木と2つの数値 a、b が与えられたとき、a と b を子孫として持つ最も深いノード（最小共通祖先：LCA）の値を求める問題を考えてみましょう。

ここで重要なポイントは、「あるノードはそれ自身の子孫にもなり得る」という点です。つまり、片方のノードがもう片方の祖先である場合、そのノード自体が答えになります。

例

以下のような二分木を考えます。

このとき、a = 6、b = 2 とすると、出力は 4 になります。値4のノードが、6と2の両方を子孫として持つ最も深いノードだからです。

解法のアプローチ

この問題は再帰を使って効率的に解くことができます。手順は以下の通りです。

• solve() メソッドを定義し、ルートノード root と探索対象の値 a、b を引数として受け取ります。
• root が null（None）の場合は -1 を返します。
• root の値が a または b のいずれかと一致する場合は、その値を返します。
• 左部分木に対して left = solve(root.left, a, b) を実行します。
• 右部分木に対して right = solve(root.right, a, b) を実行します。
• left と right の両方が -1 でない場合、現在のノードが共通祖先であるため、root の値を返します。
• 片方だけが見つかっている場合は、-1 でない方の値を返します。
• メイン処理から solve(root) を呼び出します。

Pythonでの実装例

実際のコードを見てみましょう。

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, a, b):
        if not root:
            return -1
        if root.val in (a, b):
            return root.val
        left = self.solve(root.left, a, b)
        right = self.solve(root.right, a, b)
        if -1 not in (left, right):
            return root.val
        return left if left != -1 else right

ob = Solution()
root = TreeNode(3)
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, 6, 2))

入力

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

出力

4

コードの解説

このアルゴリズムの動作を簡単に整理します。

• ベースケース： ノードが存在しない場合は -1 を返し、対象の値が見つかった時点でその値を返します。
• 後処理（ボトムアップ）： 再帰呼び出しの結果を左右それぞれから受け取り、両側で異なる対象が見つかったノードが最小共通祖先となります。
• 計算量： 各ノードを一度だけ訪問するため、時間計算量は O(n)、再帰の深さによる空間計算量は木の高さに依存し、最悪で O(n) です。

このように、再帰的な後順走査（post-order traversal）を利用することで、二分木の最小共通祖先を簡潔に求めることができます。