Tổng quan
Duyệt zigzag theo tầng đi qua cây nhị phân từng hàng một, giống duyệt theo chiều rộng thông thường, nhưng đảo chiều ở mỗi tầng: hàng đầu đọc từ trái sang phải, hàng thứ hai từ phải sang trái, hàng thứ ba lại trái sang phải.
Cái bẫy là cố đảo chiều bản thân phép duyệt. Bản sạch sẽ giữ nguyên vòng duyệt bằng hàng đợi chuẩn — luôn đẩy con trái rồi con phải — và chỉ đảo hàng đã thu được trước khi nối vào kết quả. Đổi thứ tự đẩy vào hàng đợi sẽ phá cấu trúc tầng, vì con của một hàng đã bị đảo không ra theo thứ tự mà tầng kế tiếp cần.
Duyệt Zigzag Theo Tầng hoạt động thế nào?
- Đưa nút gốc vào hàng đợi và đặt cờ hướng là trái-sang-phải.
- Ghi lại kích thước hàng đợi hiện tại — con số đó chính là đúng một tầng, chốt trước khi thêm bất kỳ nút con nào.
- Lấy ra đúng số nút đó vào một danh sách hàng, đồng thời đẩy con trái rồi con phải của từng nút vào hàng đợi.
- Nếu cờ hướng là phải-sang-trái, đảo danh sách hàng trước khi nối vào kết quả.
- Lật cờ hướng và lặp lại cho tới khi hàng đợi rỗng.
Khi nào nên dùng?
- Vẽ cây theo kiểu rắn bò — sơ đồ tổ chức và nhánh đấu loại đọc qua đọc lại theo hàng.
- Một biến thể phỏng vấn quen thuộc, kiểm tra xem bạn có hiểu cách xác định ranh giới tầng hay chỉ thuộc lòng BFS.
- Bất kỳ định dạng tuần tự hóa nào lưu cây theo từng tầng với thứ tự hàng xen kẽ.
- Mẹo chốt kích thước tầng có tính tổng quát: đó cũng chính là kỹ thuật dùng cho trung bình theo tầng, góc nhìn từ bên phải và giá trị lớn nhất mỗi tầng.
Phân tích độ phức tạp
Mỗi nút được đẩy vào và lấy ra đúng một lần, nên thời gian là O(n). Việc đảo từng hàng chạm vào mỗi phần tử nhiều nhất thêm một lần trên toàn bộ phép duyệt, nên không đổi bậc. Bộ nhớ là O(n): hàng đợi chỉ chứa tối đa một tầng tại một thời điểm, và tầng rộng nhất của cây cân bằng có khoảng n/2 nút.
Câu hỏi thường gặp
Vì sao phải chốt kích thước hàng đợi trước vòng lặp thay vì kiểm tra rỗng?
Vì các nút con đang được đẩy vào chính hàng đợi đó trong lúc bạn rút ra. Đọc kích thước từ đầu sẽ đóng băng ranh giới của tầng hiện tại; không có nó, vòng lặp sẽ chạy thẳng sang tầng sau và các hàng dính vào nhau.
Có thể dùng deque thay cho phép đảo không?
Có — đẩy vào đầu hay cuối một hàng đợi hai đầu tùy theo hướng sẽ tránh được phép đảo tường minh. Đó là cải thiện ở hằng số nhân chứ không phải bậc, và phần lớn người đọc thấy bản có phép đảo dễ hiểu hơn.
Nó còn chạy đúng trên cây mất cân bằng không?
Có. Tầng được định nghĩa theo độ sâu chứ không theo hình dạng, nên một cây chỉ là chuỗi dài sẽ cho ra n tầng, mỗi tầng một nút — khi đó cờ hướng không tạo khác biệt nhìn thấy được.