Đảo ngược cây nhị phân trong Python

Cho cây nhị phân, tạo cây đảo ngược (hoán đổi trái/phải).

Giải pháp

Đệ quy:

• Nếu gốc rỗng → return.
• Hoán đổi con trái và phải.
• Đệ quy cho cây con trái và phải.

Ví dụ

Triển khai Python:

class TreeNode: 
    def __init__(self, data, left = None, right = None): 
        self.data = data 
        self.left = left 
        self.right = right 
def make_tree(elements): 
    Tree = TreeNode(elements[0]) 
    for element in elements[1:]: 
        insert(Tree, element) 
    return Tree 
# ... (các hàm hỗ trợ in cây) 
class Solution(object): 
    def invertTree(self, root): 
        self.solve(root) 
        return root 
    def solve(self,root): 
        if not root: 
            return 
        temp = root.left 
        root.left = root.right 
        root.right = temp 
        self.solve(root.left) 
        self.solve(root.right) 
tree1 = make_tree([1,2,2,3,4,None,3]) 
ob1 = Solution() 
tree2 = ob1.invertTree(tree1) 
level_order(tree2)

Đầu vào

[1,2,2,3,4,None,3]

Đầu ra

1,2,2,3,None,4,3,