Chương trình xóa tất cả lá có giá trị chẵn khỏi cây nhị phân trong Python

Cho cây nhị phân, lặp lại xóa tất cả các nút lá có giá trị chẵn. Nếu chỉ còn gốc và gốc chẵn, cũng xóa.

Ví dụ

Cây đầu vào: (hình ảnh).
Cây sau khi xóa: (hình ảnh).

Thuật toán

1. Định nghĩa hàm solve(root):
   • Nếu root là None, trả về None.
   • Đệ quy xử lý root.left và root.right.
   • Nếu root là lá và root.data chẵn, trả về None.
   • Trả về root.

Mã nguồn Python

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)

Đầu vào / Đầu ra

Input: root = TreeNode(13) ...
Output: 13, 16, 7, 14,