Binary Tree Level Order Traversal: BFS với snapshot kích thước level

BFS mặc định không biết gì về các level. Nó chỉ liên tục dequeue node ở đầu, enqueue các con của nó, rồi tiếp tục. Nếu để nguyên như vậy, quá trình đó tạo ra một stream phẳng các giá trị theo đúng thứ tự — nhưng không có điểm đánh dấu nào cho biết "đây là chỗ level 2 kết thúc và level 3 bắt đầu." Thủ thuật snapshot là thứ chia stream đó thành các nhóm: ở đầu mỗi lần lặp, trước khi dequeue bất kỳ node nào, ta ghi lại level_size = len(queue). Tất cả những gì ta dequeue trong level_size lần lặp tiếp theo đều thuộc về level hiện tại. Những node con mà chúng thêm vào queue thuộc về level tiếp theo. Một số nguyên, được capture đúng một lần mỗi level — đó là toàn bộ cơ chế.

Constraints nói lên điều gì

Cây có tối đa 2000 node, giá trị node nằm trong [-1000, 1000]. Không có constraint nào thực sự thú vị về mặt thuật toán — 2000 node chạy trong micro giây dưới O(n), và khoảng giá trị chỉ quan trọng nếu bạn làm gì đó với các giá trị đó (ở đây không làm gì cả, chỉ lưu integer). Constraint quan trọng là cái ngầm định: root có thể là null. Bài toán cho phép cây rỗng là input hợp lệ. Đó là edge case đầu tiên, và nếu quên xử lý sẽ nhận được null-pointer exception trước khi thuật toán bắt đầu.

Cây trong ví dụ 1 trông như sau:

Level 0 chứa 3, level 1 chứa 9 và 20, level 2 chứa 15 và 7. Subtree bên trái của 20 bị thiếu — 9 và 20 đều ở cùng độ sâu dù 9 là leaf còn 20 có hai con. Sự bất đối xứng này hoàn toàn bình thường và thuật toán xử lý nó mà không cần logic đặc biệt.

BFS: cách tiếp cận tự nhiên

Queue thực thi FIFO — first in, first out. Điều đó khớp chính xác với những gì level-order traversal cần: duyệt hết tất cả ở depth 0 trước depth 1, depth 1 trước depth 2. Cấu trúc dữ liệu đang chỉ cho bạn biết phải làm gì.

Phần còn thiếu duy nhất là ranh giới giữa các level. BFS thông thường chỉ drain queue trong một pass liên tục. Để có output được nhóm lại, bạn cần biết có bao nhiêu node thuộc về level hiện tại trước khi bắt đầu lấy chúng ra. Đó là snapshot: capture len(queue) ở đầu mỗi lần lặp ngoài, rồi chạy vòng lặp trong đúng số lần đó. Bất kỳ node nào được enqueue bởi vòng lặp trong đều thuộc về level tiếp theo — chúng không ảnh hưởng đến snapshot hiện tại.

Đây là thứ tự duyệt BFS được minh họa rõ ràng:

Chạy từng bước qua ví dụ root = [3, 9, 20, null, null, 15, 7]:

Trước lần lặp 1: queue = [3]. Snapshot level_size = 1. Dequeue 3, thu thập [3], enqueue 9 và 20. Append [3] vào result.

Trước lần lặp 2: queue = [9, 20]. Snapshot level_size = 2. Dequeue 9 — không có con. Dequeue 20 — enqueue 15 và 7. Thu thập [9, 20]. Append.

Trước lần lặp 3: queue = [15, 7]. Snapshot level_size = 2. Dequeue cả hai. Không có con. Thu thập [15, 7]. Append.

Queue lúc này rỗng. Kết quả: [[3], [9, 20], [15, 7]].

Lý do len(queue) hoạt động là tinh tế nhưng quan trọng: ta capture nó trước khi vòng lặp trong chạy. Vòng lặp trong sẽ thêm các node mới vào queue, làm kích thước tăng lên — nhưng snapshot không thay đổi. Vòng lặp for _ in range(level_size) kết thúc đúng ở số đếm đúng vì level_size đã được cố định tại thời điểm level bắt đầu. Nếu thay vào đó kiểm tra while queue bên trong vòng lặp trong, bạn sẽ drain toàn bộ queue trong một pass và mất hết ranh giới level.

from collections import deque
from typing import List, Optional
 
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
 
        result = []
        queue = deque([root])
 
        while queue:
            level_size = len(queue)  # snapshot truoc vong lap trong
            current_level = []
 
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
 
            result.append(current_level)
 
        return result

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        if (root == null) return new List<IList<int>>();
 
        var result = new List<IList<int>>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            int levelSize = queue.Count;  // snapshot truoc vong lap trong
            var currentLevel = new List<int>();
 
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.Dequeue();
                currentLevel.Add(node.val);
                if (node.left != null) queue.Enqueue(node.left);
                if (node.right != null) queue.Enqueue(node.right);
            }
 
            result.Add(currentLevel);
        }
 
        return result;
    }
}

Trong Python tôi dùng collections.deque thay vì list thông thường vì popleft() là O(1) trên deque và O(n) trên list. Với cây 2000 node có thể không thấy khác biệt, nhưng deque là công cụ đúng và thói quen này sẽ hữu ích khi kích thước input không bị giới hạn.

Phương án DFS

BFS là lựa chọn tự nhiên ở đây, nhưng DFS cũng hoạt động. Ý tưởng: recursion với tham số level; khi duyệt đến node ở depth level, append giá trị của nó vào result[level], tạo sublist mới nếu chưa tồn tại.

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []
 
        def dfs(node, level):
            if not node:
                return
            if level >= len(result):
                result.append([])
            result[level].append(node.val)
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)
 
        dfs(root, 0)
        return result

public class Solution {
    public IList<IList<int>> LevelOrder(TreeNode root) {
        var result = new List<IList<int>>();
 
        void Dfs(TreeNode node, int level) {
            if (node == null) return;
            if (level >= result.Count)
                result.Add(new List<int>());
            result[level].Add(node.val);
            Dfs(node.left, level + 1);
            Dfs(node.right, level + 1);
        }
 
        Dfs(root, 0);
        return result;
    }
}

Cây recursion của cùng ví dụ cho thấy thứ tự duyệt pre-order (root, left, right) — thứ tự này tình cờ insert các giá trị từ trái sang phải trong mỗi level:

Từng bước qua ví dụ root = [3, 9, 20, null, null, 15, 7]:

• Gọi dfs(3, 0): result rỗng, tạo result[0] = [], append 3. result = [[3]].
• Gọi dfs(9, 1): level=1 >= len(result)=1, tạo result[1] = [], append 9. result = [[3], [9]].
• Gọi dfs(null, 2) (con trái của 9): return ngay.
• Gọi dfs(null, 2) (con phải của 9): return ngay.
• Gọi dfs(20, 1): result[1] đã tồn tại, append 20. result = [[3], [9, 20]].
• Gọi dfs(15, 2): tạo result[2] = [], append 15. result = [[3], [9, 20], [15]].
• Gọi dfs(null, 3) (con trái và phải của 15): cả hai return ngay.
• Gọi dfs(7, 2): result[2] đã tồn tại, append 7. result = [[3], [9, 20], [15, 7]].

Pre-order duyệt con trái của mỗi node trước con phải, nên trong level 1 ta duyệt 9 trước 20, và trong level 2 ta duyệt 15 trước 7. Thứ tự từ trái sang phải hoạt động đúng mà không cần logic thêm.

Time của DFS vẫn là O(n). Space giảm xuống O(h) trên call stack — O(log n) cho cây cân bằng, O(n) worst-case cho cây lệch. Nhưng có rủi ro thực tế trong Python: cây lệch 2000 node vượt quá recursion limit mặc định là 1000. Bạn sẽ cần sys.setrecursionlimit. Phiên bản BFS không có vấn đề này.

Tôi sẽ submit BFS. Phiên bản DFS đáng biết vì nó xuất hiện lại trong các bài toán mà bạn thực sự cần DFS nhưng vẫn muốn output được nhóm theo level.

So sánh hai approach

Cả hai approach đều thăm mỗi node đúng một lần, nên không thể tốt hơn O(n) time. Sự khác biệt về space nằm ở cấu trúc phụ trợ: BFS trả cho queue (phụ thuộc chiều rộng), DFS trả cho call stack (phụ thuộc chiều cao). Với cây cân bằng hoàn toàn, level rộng nhất có khoảng n/2 node trong khi chiều cao là log n — DFS dùng ít space phụ trợ hơn. Với cây lệch hoàn toàn (hình dạng linked list), queue không bao giờ chứa nhiều hơn 1 node trong khi call stack đạt depth n — BFS thắng. Trong thực tế với n giới hạn ở 2000, cả hai đều không vấn đề. Chọn BFS vì rõ ràng hơn.

Edge cases cần biết

Cây rỗng. root = null trả về []. Guard ở đầu cả hai solution xử lý điều này. Nếu không có guard, BFS sẽ cố enqueue null và DFS sẽ trả về kết quả rỗng anyway (base case thoát ngay) — nhưng check tường minh làm rõ ý định.

Chỉ có root. root = [1] trả về [[1]]. Queue bắt đầu với một phần tử, snapshot là 1, vòng lặp trong chạy một lần, result nhận [1] được append. Không có gì bất thường.

Cây lệch (skewed tree). Tất cả node nghiêng trái hoặc phải — cây thực chất là một linked list. BFS: queue không bao giờ chứa nhiều hơn một node tại một thời điểm, space phụ trợ là O(1). DFS: call stack đạt depth n, vượt recursion limit của Python với n > 1000. Nếu bài toán cho phép n = 10^5, đây là vấn đề thực sự và bạn sẽ muốn BFS độc quyền.

Complete binary tree. Level rộng nhất chứa khoảng n/2 node. BFS queue đạt peak ở đó. Với n = 2000, đó là khoảng 1000 node trong queue đồng thời — ổn trong thực tế nhưng đáng ghi nhớ khi bài toán tăng giới hạn n.

Nhận diện pattern

Keywords là "level by level," "level order," "breadth-first," hoặc "nodes at the same depth." Bất kỳ bài toán nào yêu cầu xử lý các node cây được nhóm theo khoảng cách từ root đều là pattern này. Nó cũng xuất hiện dưới dạng "tìm số bước tối thiểu" trong unweighted graph — BFS cho bạn shortest path, và thủ thuật level-grouping cho bạn step count.

Cụ thể hơn: nếu bài toán hỏi về thứ gì đó mỗi level thay vì thứ gì đó trên tất cả các node cùng lúc, hãy dùng snapshot. Binary Tree Right Side View hỏi về node cuối cùng mỗi level. Find Largest Value in Each Tree Row hỏi về max mỗi level. Average of Levels in Binary Tree hỏi về mean mỗi level. Tất cả đều cùng một BFS skeleton, chỉ khác phần aggregation bên trong vòng lặp.

Bài tập liên quan

• Binary Tree Right Side View (199): cùng BFS loop, chỉ lấy current_level[-1]. Buộc bạn nhận ra rằng pattern snapshot tổng quát hơn việc thu thập tất cả các giá trị.
• Binary Tree Zigzag Level Order Traversal (103): cùng BFS, đổi chiều mỗi level. Snapshot vẫn làm đúng công việc đó; vòng lặp trong có thêm direction flag.
• Maximum Depth of Binary Tree (104): cách dùng pattern đơn giản nhất — câu trả lời chỉ là số lần vòng lặp ngoài của BFS chạy.
• Binary Tree Level Order Traversal II (107): cùng kết quả nhưng đảo ngược. Chạy BFS tiêu chuẩn và reverse output list ở cuối, hoặc dùng deque và appendleft.
• Find Largest Value in Each Tree Row (515): theo dõi running max thay vì một list bên trong vòng lặp trong.