Pythonで二分木を反転するプログラム

二分木の根があるとすると、その左のサブツリーと右のサブツリーが交換され、それらの子も再帰的に交換されるように、それを反転する必要があります。

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

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

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

• メソッドsolve（）を定義します。これはノードを取ります

• ルートがnullの場合、

  • 戻る

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

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

• ルートを返す

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

例

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

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

class Solution:
   def solve(self, root):
   if not root:
      return
   root.left, root.right = self.solve(root.right), self.solve(root.left)
   return root

ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
inv = ob.solve(root)
inorder(inv)

入力

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)

出力

15, 10, 7, 5, 4,