Pythonで二分木から偶数の値を持つ葉ノードをすべて削除する方法

二分木が与えられたとき、値が偶数であるすべての葉（リーフ）ノードを繰り返し削除する問題を考えてみましょう。削除を続けた結果、根ノードだけが残り、その値が偶数であった場合は、根ノードも併せて削除します。

例えば、入力が次のような二分木だったとします。

この場合、出力は次のようになります。

解き方のアプローチ

この問題は、後順（post-order）に近い再帰処理を使うことでシンプルに解けます。子ノードを先に処理し、その結果を受けて親ノードを判定する流れです。具体的には以下の手順に従います。

• 関数 solve() を定義します。引数としてルートノードを受け取ります。

• root が null（None）の場合は、None を返します。

• root の左部分木と右部分木に対して、それぞれ再帰的に solve() を呼び出し、結果を root.left / root.right に代入します。

• root が葉ノード（左右の子を持たない）であり、かつその値が偶数であれば、None を返してノードを削除します。

• それ以外の場合は、root をそのまま返します。

ポイントは、子ノードの処理を先に行ってから親ノードを判定することです。これにより、子が削除されて新たに葉になったノードも正しく評価され、「偶数の葉」を確実に取り除くことができます。

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

実装例

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

def inorder(root):
   if root:
      inorder(root.left)
      print(root.data, end = ', ')
      inorder(root.right)

class Solution:
   def solve(self, root):
      if not root:
         return None

      root.left = self.solve(root.left)
      root.right = self.solve(root.right)

      if not root.left and not root.right and root.data % 2 == 0:
         return None
      return root

ob = Solution()
root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)
ob.solve(root)
inorder(root)

入力

root = TreeNode(13)
root.left = TreeNode(12)
root.right = TreeNode(14)
root.right.left = TreeNode(16)
root.right.right = TreeNode(22)
root.right.left.left = TreeNode(4)
root.right.left.right = TreeNode(7)

出力

13, 16, 7, 14,

処理の流れを確認しよう

この例では、まず値が偶数の葉ノード「12」「4」「22」が削除されます。「16」は元々子を持っていましたが、子が削除されたことで新しい葉になり、値が偶数なのでこちらも削除されます。最終的に残るのは「13」「7」「14」で、中順走査（inorder traversal）の出力は 13, 16, 7, 14, のようになります。

なお、このアルゴリズムの計算量は各ノードを一度だけ訪問するため O(n)、再帰によるスタックの深さは木の高さに依存し、最悪ケースで O(n) となります。