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

Cho cây nhị phân, đảo ngược (invert) cây: hoán đổi cây con trái và phải ở mọi nút (đệ quy).

Ví dụ: cây như hình → cây đảo ngược như hình.

Giải thuật (Đệ quy đơn giản)

1. Nếu là : trả về.
2. Đệ quy: .
3. Trả về .

Ví dụ minh họa

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)  # Output: 15, 10, 7, 5, 4,

Đầ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,