Pythonで二分木のすべてのノードの値が同じかどうかをチェックするプログラム

問題の概要

二分木が与えられたとき、その木に含まれるすべてのノードが同じ値を持っているかどうかを判定することを考えます。

例えば、次のような二分木が入力として与えられた場合、

すべてのノードが同じ値を持っているため、出力は True になります。

解決のアプローチ

この問題は、再帰を使ってシンプルに解くことができます。以下の手順に従います。

• solve() 関数を定義します。この関数は root(現在のノード)と val(比較対象の値)を引数として受け取ります。

• root が null(None)の場合は、True を返します。空の部分木は条件を満たしているとみなせるためです。

• val が未定義の場合は、root の値を val として設定します。これにより、最初のノードの値が基準値になります。

• 「root の値が val と等しい」かつ「左部分木に対する solve() の結果が True」かつ「右部分木に対する solve() の結果が True」である場合に True を返します。

実装例

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

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

class Solution:
   def solve(self, root, val=None):
      if not root:
         return True
      if val is None:
         val = root.val
      return root.val == val and self.solve(root.left, val) and self.solve(root.right, val)

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)
print(ob.solve(root))

入力

root = TreeNode(5)
root.left = TreeNode(5)
root.right = TreeNode(5)
root.left.left = TreeNode(5)
root.left.right = TreeNode(5)

出力

True

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量は O(n)(n はノード数)です。また、再帰の深さは木の高さに依存するため、空間計算量は最悪の場合 O(n)、平衡な木であれば O(log n) となります。