Chương trình xóa tất cả các nút chỉ có một nút con khỏi cây nhị phân trong Python?

Giả sử chúng ta có một gốc cây nhị phân; chúng tôi phải loại bỏ tất cả các nút chỉ có một nút con.

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 có tên là giải quyết (), phương thức này sẽ lấy gốc cây

• nếu root là null thì

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

• nếu bên trái của thư mục gốc là null và bên phải của thư mục gốc là null, thì

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

• nếu bên trái của thư mục gốc là null, thì

  • trả về giải quyết (quyền của thư mục gốc)

• nếu quyền của thư mục gốc là null, thì

  • trả về giải quyết (bên trái của thư mục gốc)

• left of root:=giải quyết (left 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

Ví dụ

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

def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)

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

      if not root.left and not root.right:
         return root

      if not root.left:
         return self.solve(root.right)

      if not root.right:
         return self.solve(root.left)

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

      return root

ob = Solution()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)

res = ob.solve(root)
print_tree(res)

Đầu vào

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.right.right = TreeNode(5)
root.left.left.right = TreeNode(6)
root.right.right.left = TreeNode(7)
root.right.right.right = TreeNode(8)

Đầu ra

6, 1, 7, 5, 8,