Làm thế nào để đảo ngược một Cây nhị phân (Invert Binary Tree) và phân tích ảnh hưởng của nó đến bộ nhớ hệ thống?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Đảo ngược một Cây nhị phân nghĩa là với mọi nút trong cây, chúng ta hoán đổi con trỏ bên trái và con trỏ bên phải của nó. Thao tác này có thể thực hiện hiệu quả bằng cả đệ quy (DFS) hoặc khử đệ quy sử dụng Queue (BFS).
Ví dụ mã nguồn minh họa
def invertTree(root: TreeNode) -> TreeNode:
    if not root:
        return None

# Hoán đổi con trái và con phải
    root.left, root.right = root.right, root.left

# Đệ quy cho cây con
    invertTree(root.left)
    invertTree(root.right)

return root
Lưu ý kinh nghiệm thực chiến

Độ phức tạp: Thời gian thực thi là O(N) vì mỗi nút được ghé thăm một lần để hoán đổi. Không gian bộ nhớ tiêu tốn là O(H) cho Stack gọi hàm đệ quy.
Câu hỏi kinh điển: Đây là bài toán nổi tiếng trong ngành công nghệ thông tin xuất phát từ câu chuyện phỏng vấn tại các tập đoàn lớn. Khi giải quyết, hãy chú ý xử lý trường hợp nút gốc bằng None để tránh lỗi AttributeError.

Làm thế nào để đảo ngược một Cây nhị phân (Invert Binary Tree) và phân tích ảnh hưởng của nó đến bộ nhớ hệ thống?

Bản chất cơ chế hoạt động

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi binary tree liên quan cùng chủ đề