二分木における最小共通祖先（Lowest Common Ancestor）の探索

6759 ワード
データ構造 Python 競技プログラミング アルゴリズム Python テキストリンク

概要

木構造における最小共通祖先（Lowest Common Ancestor: LCA）とは、ある二つのノードが与えられた時、その両方を自身以下に持つノードのうち、最も低い（葉に近い）位置にあるノードのことを指します。一方のノードがもう一方のノードの直接の祖先となっている場合は、直接の祖先となっているノードがLCAとなります。例えば以下の二分木において、6と4のLCAは5、0と1のLCAは1となります。

LCAを探索するアルゴリズムは複数ありますが、本記事では各ノードから自身の祖先を辿っていき、最初に遭遇する共通の祖先を探し出す手法を紹介します。

方針

各ノードから自身の祖先を辿ろうとする場合、各ノードは自身の親を知っていなければなりません。そこで方針としては下記になります。

  1. 各ノードを巡回し、各ノードの親をdictionaryに保存しておく
  2. 与えられた二つのノードのうち、一方のノードから親を辿っていき、rootに達するまでに辿ったノード（全ての祖先）をsetに保存しておく
  3. もう一方のノードから親を辿っていき、2で保存したsetに含まれるノードが現れた時、それが共通の祖先（LCA）となる

注：1では与えられた二つのノードの親が見つかった時点で巡回を打ち切る方が効率的ですが、今回は便宜上全ノードを巡回することにします。

実装例

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

class Solution(object):
    # 各ノードをDFSで巡回しつつ、親ノードをdictionaryに保存していく
    def traverse(self, node, parents):
        if node is None:
            return parents
        if node.left is not None:
            parents[node.left] = node
            self.traverse(node.left, parents)
        if node.right is not None:
            parents[node.right] = node
            self.traverse(node.right, parents)

        return parents

    # ノードp, qのLCAを探索するメソッド
    def lowestCommonAncestor(self, root, p, q):
        # 各ノードをkey、その親をvalueに持つdictionaryを作成しておく
        parents = {root: None}
        parents = self.traverse(root, parents)

        # 一方のノード（ここではp）の祖先を保存しておくためのsetを用意する
        ancestors = set()
        # 自分自身がLCAになる可能性もあるため、まずは自身をセットする
        parent = p

        # pの親を辿っていき、祖先となるノードを全てsetに保存していく
        while parent is not None:
            ancestors.add(parent)
            parent = parents[parent]

        # 次にqから親を辿っていき、pの祖先とぶつかった時点でLCAとみなす
        node = q
        while node not in ancestors:
            node = parents[node]

        return node

参考

Lowest Common Ancestor (Wikipedia)
最小共通祖先