Pythonのバイナリツリーから偶数の値を持つすべての葉を削除するプログラム

二分木があるとすると、値が偶数のすべての葉を繰り返し削除します。すべてを削除した後、値が偶数のルートしかない場合は、それも削除されます。

したがって、入力が次のような場合

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

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これが定着します

• ルートがnullの場合、

  • nullを返す

• ルートの左側：=solve（ルートの左側）

• ルートの権利：=solve（ルートの権利）

• ルートがリーフで、ルートのデータが偶数の場合、

  • nullを返す

• ルートを返す

理解を深めるために、次の実装を見てみましょう-

例

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,