Làm thế nào để tính chiều cao của một Cây nhị phân và tối ưu hóa quá trình duyệt cây trong lập trình ứng dụng thực tế?

Question

Accepted Answer

Bản chất cơ chế hoạt động
Chiều cao của một Cây nhị phân (Binary Tree) được định nghĩa là số cạnh dài nhất từ nút gốc (Root) đến một nút lá (Leaf) sâu nhất. Trong lập trình, để tính chiều cao này, chúng ta thường sử dụng phương pháp đệ quy dựa trên thuật toán duyệt cây theo chiều sâu (DFS - Depth-First Search).
Ví dụ mã nguồn minh họa
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    if not root:
        return 0
    left_height = maxDepth(root.left)
    right_height = maxDepth(root.right)
    return max(left_height, right_height) + 1
Lưu ý kinh nghiệm thực chiến

Độ phức tạp: Độ phức tạp thời gian là O(N) với N là tổng số nút trong cây vì thuật toán phải duyệt qua mọi nút đúng một lần. Độ phức tạp không gian là O(H) với H là chiều cao của cây do vùng nhớ Stack dành cho các lời gọi đệ quy.
Tràn bộ nhớ Stack (Stack Overflow): Đối với các cây bị lệch sâu (Skewed Tree) trong trường hợp xấu nhất khi H = N, đệ quy có thể gây lỗi tràn bộ nhớ. Ở cấp độ Junior, bạn nên lưu ý sử dụng duyệt theo chiều rộng (BFS - Breadth-First Search) dùng Queue để khử đệ quy khi cần xử lý các cây có cấu trúc không cân bằng.

Làm thế nào để tính chiều cao của một Cây nhị phân và tối ưu hóa quá trình duyệt cây trong lập trình ứng dụng thực tế?

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ủ đề