Chương trình đảo ngược cây nhị phân trong Python

Giả sử chúng ta có một gốc cây nhị phân, chúng ta phải đảo ngược nó để cây con bên trái và cây con bên phải của nó được trao đổi và con của chúng cũng được trao đổi một cách đệ quy.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức giải quyết (), điều này sẽ sử dụng nút

• nếu root là null thì

  • trở lại

• left of root:=giải quyết (right of root)

• quyền của người chủ:=giải quyết (quyền của người gốc)

• trả về thư mục gốc

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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)

Đầu vào

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

Đầu ra

15, 10, 7, 5, 4,