Pythonで二分木から最大のBST（二分探索木）部分木を見つけるプログラム

問題の概要

二分木が与えられたとき、その中に含まれる部分木のうち、二分探索木（BST）の条件を満たす最大の部分木を見つけ出し、その根ノードを返すことを考えます。

二分探索木とは、各ノードについて「左の子の値 ≤ ノード自身の値 ≤ 右の子の値」という大小関係が保たれる二分木のことです。

たとえば、上のような入力が与えられた場合、出力は次のようになります。

解法の考え方

この問題は、木を再帰的に走査しながら、各ノードを根とする部分木がBSTの条件を満たしているかを順に判定していくことで解けます。全体の流れは以下のとおりです。

• 最大ノード数を記録する変数 c := 0 と、答えとなる根ノード m := null を用意します。
• 関数 recurse(node) を定義します。
  • node が null でない場合：
    • left_val := recurse(node の左の子)
    • right_val := recurse(node の右の子)
    • count := −∞（負の無限大）で初期化します。
    • 「左の子が null、または 左の子の値 ≤ node の値」かつ「右の子が null、または node の値 ≤ 右の子の値」という条件を満たす場合は、count := left_val + right_val + 1 とします。
    • count > c であれば、c := count、m := node として記録を更新します。
    • count を返します。
  • node が null の場合は 0 を返します。
• recurse(root) を呼び出した後、m を返します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

class TreeNode:
    def __init__(self, val, left = None, right = None):
        self.val = val
        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):
    if root is not None:
        print_tree(root.left)
        print(root.val, end = ', ')
        print_tree(root.right)

def solve(root):
    c, m = 0, None

    def recurse(node):
        if node:
            nonlocal c, m
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left == None or node.left.val <= node.val) and (node.right == None or node.val <= node.right.val):
                count = left_val + right_val + 1
            if count > c:
                c = count
                m = node
            return count
        return 0

    recurse(root)
    return m

tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))

入力

tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))

出力

3, 4, 5,

まとめ

このアルゴリズムでは、木を後順（post-order）で走査し、子ノードの判定結果を先に集めてから親ノードの条件判定を行うのがポイントです。各ノードを一度だけ訪問するため、時間計算量は O(n)、再帰呼び出しに必要な空間計算量は木の高さに依存して O(h) となります。二分木とBSTの性質を組み合わせた典型的な再帰処理の練習問題として、ぜひ理解を深めてください。