Pythonで配列が二分探索木（BST）の中間順巡回を表しているかどうかを判定する方法

数値の配列 nums が与えられたとき、その配列がある二分探索木（Binary Search Tree）を中間順巡回（inorder traversal）した結果と一致する順序で要素を保持しているかどうかを判定します。

例えば、入力が nums = [5, 8, 15, 18, 20, 26, 39] の場合、この配列は以下の二分探索木を中間順巡回した結果と一致するため、出力は True になります。

解法のポイント

ここで重要な性質があります。それは、二分探索木を中間順巡回すると、必ず昇順にソートされた要素列が得られるというものです。したがって、この問題は「配列が昇順に並んでいるかどうかを確認する」ことに帰着できます。

アルゴリズムの手順

• 配列 nums のサイズを取得します。
• サイズが 0 または 1 の場合は、要素が1つもしくは存在しないため、常に条件を満たすので True を返します。
• インデックス 1 からサイズ - 1 までループし、隣接する要素を比較します。nums[i - 1] > nums[i] となる箇所があれば、昇順になっていないため False を返します。
• すべての比較で問題がなければ、True を返します。

それでは、実際の実装を見て理解を深めましょう。

実装例

def solve(nums):
    size = len(nums)
    if size == 0 or size == 1:
        return True
    for i in range(1, size):
        if nums[i - 1] > nums[i]:
            return False
    return True

nums = [5, 8, 15, 18, 20, 26, 39]
print(solve(nums))

入力

[5, 8, 15, 18, 20, 26, 39]

出力

True

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) となります。木構造を実際に構築して巡回する必要がないため、非常に効率的な判定方法です。