Pythonで二分木が完全二分木かどうかを判定するプログラム

完全二分木とは

二分木が与えられたとき、その木が完全二分木(complete binary tree)であるかどうかを判定することを考えます。完全二分木とは、最後のレベルを除くすべてのレベルがノードで埋め尽くされており、最後のレベルのノードはすべて可能な限り左側に寄せられている二分木のことです。

例えば、次のような二分木が入力として与えられた場合、出力は True になります。

アルゴリズム(BFSによる判定方法)

この問題は、幅優先探索(BFS)を使って効率的に解けます。木をレベル順に走査し、初めて空のノード(None)が出現した後に再びノードが出現したら、その木は完全二分木ではないと判断できます。手順は以下の通りです。

• 両端キュー(deque)q を用意する。
• ルートを q の末尾に追加する。
• フラグ flag を False で初期化する。
• q が空になるまで、以下を繰り返す。
  • temp に q の左端から取り出した要素を代入する。
  • temp が None の場合は、flag を True にする。
  • flag が True になっているのに temp が None でない場合は、False を返す。
  • それ以外の場合は、temp の左の子と右の子を q の末尾に追加する。
• ループが正常に終了したら、True を返す。

Pythonでの実装例

from collections import deque

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

class Solution:
    def solve(self, root):
        q = deque()
        q.append(root)
        flag = False
        while q:
            temp = q.popleft()
            if not temp:
                flag = True
            elif flag and temp:
                return False
            else:
                q.append(temp.left)
                q.append(temp.right)
        return True

ob = Solution()
root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)
print(ob.solve(root))

入力

root = TreeNode(9)
root.left = TreeNode(7)
root.right = TreeNode(10)
root.left.left = TreeNode(6)
root.left.right = TreeNode(8)

出力

True

計算量

このアルゴリズムでは各ノードを一度ずつ訪問するため、時間計算量は O(n)(n はノード数)です。また、キューには最大で O(n) 個の要素が格納される可能性があるため、空間計算量も O(n) となります。