Pythonで二分木の最も深い葉ノードの最小共通祖先（LCA）を求める方法

根付き二分木が与えられたとき、その最も深い葉ノードの最小共通祖先（LCA: Lowest Common Ancestor）を返す問題を考えてみましょう。この問題を解く前に、以下の定義を確認しておきます。

前提となる定義

• 二分木のノードは、子を持たない場合に限り「葉ノード」と呼ばれます。
• 木の根（ルート）の深さは0とし、あるノードの深さがdであるとき、その子ノードの深さはd+1になります。
• ノード集合Sの最小共通祖先とは、S内のすべてのノードがその部分木に含まれるような、最も深いノードAのことです。

たとえば、入力が [1,2,3,4,5] の二分木である場合、出力は [2,4,5] となります。これは、最も深い葉ノードが4と5であり、それらの共通祖先が2だからです。

解法のアプローチ

この問題は、再帰的な後順走査（ポストオーダー）を用いることで効率的に解けます。各ノードについて「その部分木の最大深さ」と「最深葉のLCA候補」をペアで返していくのがポイントです。

solve() メソッドの設計

1. solve(node) を定義します。このメソッドは [深さ, LCA候補ノード] のリストを返します。
2. node が存在しない場合は [0, None] を返します。
3. 左右の子がどちらも存在しない（葉ノード）場合は [1, node] を返します。
4. 左部分木の結果を d1, l に、右部分木の結果を d2, r にそれぞれ格納します。
5. d1 > d2 の場合は [d1 + 1, l] を返します（より深い側のLCAを引き継ぐ）。
6. d2 > d1 の場合は [d2 + 1, r] を返します。
7. 両者の深さが等しい場合は、現在のノードが共通祖先となるため [d1 + 1, node] を返します。

メイン処理

1. list := solve(root) を呼び出します。
2. list[1]（LCA候補ノード）を返します。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

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

def insert(temp, data):
    que = []
    que.append(temp)
    while (len(que)):
        temp = que[0]
        que.pop(0)
        if (not temp.left):
            if data is not None:
                temp.left = TreeNode(data)
            else:
                temp.left = TreeNode(0)
            break
        else:
            que.append(temp.left)
        if (not temp.right):
            if data is not None:
                temp.right = TreeNode(data)
            else:
                temp.right = TreeNode(0)
            break
        else:
            que.append(temp.right)

def make_tree(elements):
    Tree = TreeNode(elements[0])
    for element in elements[1:]:
        insert(Tree, element)
    return Tree

def print_tree(root):
    # 中順走査（inorder traversal）で出力
    if root is not None:
        print_tree(root.left)
        print(root.data, end = ', ')
        print_tree(root.right)

class Solution(object):
    def lcaDeepestLeaves(self, root):
        return self.solve(root)[1]

    def solve(self, node):
        if not node:
            return [0, None]
        if not node.left and not node.right:
            return [1, node]
        d1, l = self.solve(node.left)
        d2, r = self.solve(node.right)
        if d1 > d2:
            return [d1 + 1, l]
        elif d2 > d1:
            return [d2 + 1, r]
        return [d1 + 1, node]

ob = Solution()
root = make_tree([1,2,3,4,5])
print_tree(ob.lcaDeepestLeaves(root))

入力

[1,2,3,4,5]

出力

4, 2, 5,

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量はO(n)（nはノード数）となります。また、再帰呼び出しのスタックの深さは木の高さに依存するため、空間計算量は最悪の場合O(n)です。木が平衡に近い場合はO(log n)に抑えられます。