Pythonで親ポインタを使って二分木の最小共通祖先(LCA)を求める方法

二分木と、その中の2つの特定のノード x・y が与えられたとします。このとき、2つのノードの最小共通祖先(Lowest Common Ancestor:LCA)を二分木の中から見つける必要があります。二分木における最小共通祖先とは、ノード x と y の両方が子孫となる最も深いノードのことです。なお、あるノードは自分自身の子孫でもあるとみなされる点に注意してください。該当するノードを見つけ、結果として返します。

今回扱うツリーのノード構造は以下のとおりです。

TreeNode:
    data: <整数>
    left: <TreeNode へのポインタ>
    right: <TreeNode へのポインタ>
    parent: <TreeNode へのポインタ>

この問題では、解を求める際に親ポインタ(parent)を活用することがポイントになります。

入力例と出力

たとえば、次のような二分木が与えられたとします。

ここで x = 3、y = 7 とした場合、出力は 5 になります。3 と 7 はどちらも 5 の子孫であるためです。

解法のステップ

この問題は、次の手順で解くことができます。

1. path_p_r という新しいリストを作成します。
2. x が null でない間、次の処理を繰り返します。
   • path_p_r の末尾に x を追加する。
   • x を x の親ノードに更新する。
3. y が null でない間、次の処理を繰り返します。
   • y が path_p_r に存在する場合は、y を返す。
   • y を y の親ノードに更新する。

考え方を整理すると、「まずノード x から根に向かう経路上のすべてのノードを記録し、その後ノード y から根へ向かいながら、最初に一致したノードを答えとする」というシンプルなものです。x と y の共通の祖先は必ず x から根までの経路上に存在するため、この方法で必ず LCA を見つけられます。

Pythonでの実装例

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

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

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

def search_node(root, element):
   if root is None:
      return None
   if root.data == element:
      return root
   res1 = search_node(root.left, element)
   if res1:
      return res1
   return search_node(root.right, element)

def solve(x, y):
   path_p_r = []
   while x:
      path_p_r.append(x)
      x = x.parent
   while y:
      if y in path_p_r:
         return y
      y = y.parent

root = make_tree([5, 3, 7, 2, 4, 1, 7, 6, 8, 10])
print(solve(search_node(root, 3), search_node(root, 7)).data)

入力

[5, 3, 7, 2, 4, 1, 7, 6, 8, 10], 3, 7

出力

5

計算量について

木の高さを h とすると、ノード x から根までの経路をリストに保存するため、空間計算量は O(h) です。時間計算量は、y から根へ辿る各ステップでリスト内の線形探索(in 演算子)を行うため、最悪で O(h²) となります。経路を set(集合)に保存してメンバーシップ判定を O(1) にすれば、全体の計算量を O(h) まで改善できます。