Pythonで二分木の指定した垂直レベルがソートされているかどうかを判定する方法

問題の概要

二分木が与えられたとき、指定された垂直レベル（vertical level）に属するノードの値が昇順にソートされているかどうかを判定する問題です。垂直レベルとは、木を横から見たときに同じ縦位置に並ぶノードのグループを指し、ルートのレベルを 0 とすると、左へ移動するごとに -1、右へ移動するごとに +1 となります。

なお、2つのノードが画面上で重なって見える場合でも、それぞれが属するレベル内での並び順がソートされていればよいものとします。

例として level = -1 を指定した場合、そのレベルに含まれる要素は「3, 7」であり、昇順に並んでいるため、出力は True になります。

解法のアプローチ：BFS（幅優先探索）を活用

この問題は、BFS（幅優先探索）を使うことで効率的に解けます。deque（両端キュー）を利用して各ノードとその垂直レベルをペアで管理しながら走査し、対象レベルのノード値が常に直前の値以上であることを確認していきます。

アルゴリズムの手順

• ルートが null の場合は True を返す
• previous_value を負の無限大（INT_MIN）で初期化する
• current_level を 0 に初期化する
• current_node を値 0 の新しいツリーノードとして初期化する
• deque 型のキュー q を定義する
• (root, 0) を q の末尾に追加する
• q が空になるまで以下を繰り返す：
  • current_node に q[0][0] を代入する
  • current_level に q[0][1] を代入する
  • q の左端から要素を取り除く
  • current_level が指定された level と一致する場合：
    • previous_value <= current_node.val であれば、previous_value を current_node.val で更新する
    • そうでなければ False を返す
  • current_node.left が存在すれば、(current_node.left, current_level - 1) を q の末尾に追加する
  • current_node.right が存在すれば、(current_node.right, current_level + 1) を q の末尾に追加する
• ループが完了したら True を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

from collections import deque
from sys import maxsize

INT_MIN = -maxsize

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

def are_elements_sorted(root, level):
    if root is None:
        return True
    previous_value = INT_MIN
    current_level = 0
    current_node = TreeNode(0)
    q = deque()
    q.append((root, 0))
    while q:
        current_node = q[0][0]
        current_level = q[0][1]
        q.popleft()
        if current_level == level:
            if previous_value <= current_node.val:
                previous_value = current_node.val
            else:
                return False
        if current_node.left:
            q.append((current_node.left, current_level - 1))
        if current_node.right:
            q.append((current_node.right, current_level + 1))
    return True

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)

level = -1
print(are_elements_sorted(root, level))

入力

root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)

出力

True

計算量の目安

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n) です。また、キューには最大で木の幅に相当するノードが格納されるため、空間計算量も O(n) となります（n は二分木のノード総数）。BFS を使うことで、深さ優先探索のように再帰スタックを意識することなく、レベルごとの値を順番に検証できるのがポイントです。