โปรแกรมแปลงไบนารีทรีใน Python

สมมติว่าเรามีรูทแบบไบนารี เราต้องกลับมันเพื่อให้มีการแลกเปลี่ยนทรีย่อยทางซ้ายและทรีย่อยทางขวา และลูกหลานของพวกมันจะถูกแลกเปลี่ยนแบบเรียกซ้ำด้วย

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการแก้ปัญหา () สิ่งนี้จะใช้โหนด

• ถ้ารูทเป็นโมฆะ

  • กลับ

• ทางซ้ายของรูท :=แก้ (ทางขวาของรูท)

• ทางขวาของรูท :=แก้ (ทางขวาของรูท)

• คืนค่ารูท

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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,