Serialize và Deserialize Binary Tree: mã hóa cấu trúc, không chỉ giá trị

Bài toán cho bạn toàn quyền tự do trong cách encode cây. Chính sự tự do đó là cái bẫy. Bản năng đầu tiên là ghi lại giá trị các node — nhưng giá trị thôi không đủ để tái tạo một cây duy nhất. String "1 2 3" có thể mô tả một root với hai con, hoặc một chuỗi lệch, hoặc nhiều hình dạng khác. Bạn cần encode cả cấu trúc, và câu hỏi là bằng cách nào.

Hai encoding tự nhiên xuất phát từ hai chiến lược duyệt cây quen thuộc: BFS level-order (cùng cách LeetCode trình bày test case của mình) và DFS preorder (cách đệ quy phản chiếu cách bạn xây một cây từ mô tả đệ quy). Cả hai đều đúng. Cả hai đều O(N) time và space. Nhưng chúng khác nhau về độ dài string, độ phức tạp của decode, và stack behavior trong điều kiện constraints của bài này.

Đề bài

Thiết kế thuật toán để serialize một binary tree thành string và deserialize string đó trở lại cấu trúc cây ban đầu. Không có ràng buộc về cách thuật toán hoạt động — chỉ cần đảm bảo round-trip là lossless. Bài gốc: LeetCode 297.

Ràng buộc:
- Số node trong cây nằm trong khoảng [0, 10^4].
- -1000 <= Node.val <= 1000

Constraints nói gì

Cây có [0, 10^4] node, giá trị trong [-1000, 1000]. Không con số nào đáng sợ riêng lẻ, nhưng cộng lại chúng xác định một vài điều đáng đặt tên trước khi viết code.

Số node tối đa 10^4 loại trừ mọi cách tiếp cận O(N^2) -- dù với single traversal bạn không bao giờ có nguy cơ đó ở đây. Quan trọng hơn với giải pháp DFS, 10^4 node nghĩa là recursion stack có thể sâu 10^4 frame trong một cây lệch hoàn toàn. Giới hạn recursion mặc định của Python là 1000. Đó là rủi ro thực sự. Trong môi trường production bạn hoặc phải đặt sys.setrecursionlimit hoặc dùng explicit stack cho DFS. BFS tránh hoàn toàn vấn đề này.

Giá trị trong [-1000, 1000] bao gồm số âm và số 0. Dấu âm là một phần của giá trị; ký tự delimiter không được va chạm với dấu trừ. Dấu phẩy hoạt động tốt vì giá trị node là số nguyên, không có dấu phẩy trong chuỗi biểu diễn của chúng. Marker null # và string "null" đều ổn với lý do tương tự.

Cây rỗng (N = 0) nằm trong phạm vi. Cả hai approach phải xử lý trường hợp root là None/null ngay từ đầu.

Approach 1: BFS level-order

BFS level-order ghi giá trị theo từng hàng, từ trái sang phải, dùng null để biểu diễn các con vắng mặt. Đây chính xác là format LeetCode dùng trong test case. Insight mấu chốt cho decode: mỗi node được dequeue sẽ lấy hai giá trị tiếp theo làm con trái và con phải của nó.

from collections import deque
 
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
 
class Codec:
    def serialize(self, root: TreeNode) -> str:
        if not root:
            return ""
 
        result = []
        queue = deque([root])
 
        while queue:
            node = queue.popleft()
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("null")
 
        # cắt bỏ các "null" ở cuối -- không cần thiết cho tái tạo
        while result and result[-1] == "null":
            result.pop()
 
        return ",".join(result)
 
    def deserialize(self, data: str) -> TreeNode:
        if not data:
            return None
 
        values = data.split(",")
        root = TreeNode(int(values[0]))
        queue = deque([root])
        i = 1
 
        while queue and i < len(values):
            node = queue.popleft()
 
            if i < len(values) and values[i] != "null":
                node.left = TreeNode(int(values[i]))
                queue.append(node.left)
            i += 1
 
            if i < len(values) and values[i] != "null":
                node.right = TreeNode(int(values[i]))
                queue.append(node.right)
            i += 1
 
        return root

using System;
using System.Collections.Generic;
 
public class Codec {
 
    public string serialize(TreeNode root) {
        if (root == null) return "";
 
        var result = new List<string>();
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
 
        while (queue.Count > 0) {
            TreeNode node = queue.Dequeue();
            if (node != null) {
                result.Add(node.val.ToString());
                queue.Enqueue(node.left);
                queue.Enqueue(node.right);
            } else {
                result.Add("null");
            }
        }
 
        // cắt bỏ các "null" ở cuối
        while (result.Count > 0 && result[result.Count - 1] == "null")
            result.RemoveAt(result.Count - 1);
 
        return string.Join(",", result);
    }
 
    public TreeNode deserialize(string data) {
        if (string.IsNullOrEmpty(data)) return null;
 
        string[] values = data.Split(',');
        TreeNode root = new TreeNode(int.Parse(values[0]));
        var queue = new Queue<TreeNode>();
        queue.Enqueue(root);
        int i = 1;
 
        while (queue.Count > 0 && i < values.Length) {
            TreeNode node = queue.Dequeue();
 
            if (i < values.Length && values[i] != "null") {
                node.left = new TreeNode(int.Parse(values[i]));
                queue.Enqueue(node.left);
            }
            i++;
 
            if (i < values.Length && values[i] != "null") {
                node.right = new TreeNode(int.Parse(values[i]));
                queue.Enqueue(node.right);
            }
            i++;
        }
 
        return root;
    }
}

Đi qua ví dụ

Cây [1, 2, 3, null, null, 4, 5]:

Serialize, từng level:

Queue: [1]
  Dequeue 1  -> result: ["1"],         enqueue 2, 3
Queue: [2, 3]
  Dequeue 2  -> result: ["1","2"],     enqueue null, null
  Dequeue 3  -> result: ["1","2","3"], enqueue 4, 5
Queue: [null, null, 4, 5]
  Dequeue null -> result: [...,"null"]
  Dequeue null -> result: [...,"null"]
  Dequeue 4    -> result: [...,"4"],   enqueue null, null
  Dequeue 5    -> result: [...,"5"],   enqueue null, null
Queue: [null, null, null, null]
  Bốn null -> "null","null","null","null"

Trước trim: "1,2,3,null,null,4,5,null,null,null,null"
Sau trim:   "1,2,3,null,null,4,5"

Deserialize của "1,2,3,null,null,4,5":

values = ["1","2","3","null","null","4","5"]
root = TreeNode(1),  queue = [1],  i = 1

Dequeue 1:  values[1]="2"   -> 1.left=2,  queue=[2];  i=2
            values[2]="3"   -> 1.right=3, queue=[2,3]; i=3
Dequeue 2:  values[3]="null"-> bỏ qua;    i=4
            values[4]="null"-> bỏ qua;    i=5
Dequeue 3:  values[5]="4"   -> 3.left=4,  queue=[4];  i=6
            values[6]="5"   -> 3.right=5, queue=[4,5]; i=7
Dequeue 4:  i=7 >= length, vòng lặp kết thúc

Kết quả: cây ban đầu được tái tạo.

Complexity

Time: O(N) cho cả serialize và deserialize. Mỗi node được enqueue và dequeue đúng một lần.

Space: O(N) cho queue và output string. Ở level rộng nhất của cây đầy đủ, queue chứa O(N/2) phần tử.

Approach 2: DFS preorder

Preorder traversal thăm root trước các con của nó. Thuộc tính quan trọng mà điều này mang lại: khi bạn deserialize, mỗi giá trị bạn đọc là chính xác root của subtree tiếp theo cần xây dựng. Bạn không cần bookkeeping về slot con nào đang được điền -- cấu trúc đệ quy tự xử lý điều đó.

Null marker ở đây là #. Khi deserializer đọc #, nó trả về None ngay lập tức và node cha nhận về một null child. Không cần look-ahead, không cần queue-based bookkeeping.

class Codec:
    def serialize(self, root: TreeNode) -> str:
        parts = []
 
        def preorder(node):
            if not node:
                parts.append("#")
                return
            parts.append(str(node.val))
            preorder(node.left)
            preorder(node.right)
 
        preorder(root)
        return ",".join(parts)
 
    def deserialize(self, data: str) -> TreeNode:
        it = iter(data.split(","))
 
        def build():
            val = next(it)
            if val == "#":
                return None
            node = TreeNode(int(val))
            node.left = build()
            node.right = build()
            return node
 
        return build()

using System;
using System.Collections.Generic;
 
public class Codec {
 
    public string serialize(TreeNode root) {
        var parts = new List<string>();
 
        void Preorder(TreeNode node) {
            if (node == null) {
                parts.Add("#");
                return;
            }
            parts.Add(node.val.ToString());
            Preorder(node.left);
            Preorder(node.right);
        }
 
        Preorder(root);
        return string.Join(",", parts);
    }
 
    public TreeNode deserialize(string data) {
        string[] values = data.Split(',');
        int index = 0;
 
        TreeNode Build() {
            if (index >= values.Length || values[index] == "#") {
                index++;
                return null;
            }
            var node = new TreeNode(int.Parse(values[index++]));
            node.left = Build();
            node.right = Build();
            return node;
        }
 
        return Build();
    }
}

Trace preorder

Cùng cây [1, 2, 3, null, null, 4, 5]. Preorder thăm theo thứ tự: 1, toàn bộ subtree trái, sau đó toàn bộ subtree phải.

Output serialize: "1,2,#,#,3,4,#,#,5,#,#"

Trace deserialize -- iterator đọc từ trái sang phải, các lời gọi đệ quy tiêu thụ giá trị theo cùng thứ tự preorder:

build(): đọc "1" -> node=1
  node.left  = build(): đọc "2" -> node=2
    node.left  = build(): đọc "#" -> trả về None
    node.right = build(): đọc "#" -> trả về None
    trả về node=2
  node.right = build(): đọc "3" -> node=3
    node.left  = build(): đọc "4" -> node=4
      node.left  = build(): đọc "#" -> trả về None
      node.right = build(): đọc "#" -> trả về None
      trả về node=4
    node.right = build(): đọc "5" -> node=5
      node.left  = build(): đọc "#" -> trả về None
      node.right = build(): đọc "#" -> trả về None
      trả về node=5
    trả về node=3
  trả về node=1

Iterator được tiêu thụ đúng một lần, theo cùng thứ tự serializer đã ghi. Sự đối xứng đó là lý do tại sao DFS hoạt động mà không cần bất kỳ queue hay index bookkeeping nào.

Complexity

Time: O(N). Mỗi node tạo ra đúng một token giá trị khi serialize; mỗi token được tiêu thụ đúng một lần khi deserialize.

Space: O(N) cho output string. Độ sâu call stack là O(H), trong đó H là chiều cao cây. Với cây cân bằng là O(log N). Với cây lệch là O(N) -- và với 10^4 node, đó là 10^4 stack frame, vượt quá giới hạn mặc định 1000 của Python. C# cũng dùng lời gọi đệ quy và sẽ gặp vấn đề tương tự ở quy mô lớn.

Đây là điểm duy nhất DFS có nhược điểm thực sự so với BFS trong bài này.

Các edge case quan trọng

Cây rỗng. root = None / null. BFS serializer trả về "" ngay lập tức; BFS deserializer trả về None với string rỗng. DFS serializer xuất ra "#" cho null root; DFS deserializer đọc "#" và trả về None. Cả hai round-trip đúng. Test case này cần kiểm tra đầu tiên.

Node đơn. root = [5]. BFS encode thành "5", decode thành node không có con. DFS encode thành "5,#,#" -- hai marker # cho con trái và phải. Cả hai decode lại thành node ban đầu. Các marker thêm trong DFS là thông tin cấu trúc, không phải nhiễu.

Cây lệch trái hoặc phải. Chuỗi 10^4 node là killer cho DFS recursion. BFS xử lý nó iteratively với queue không bao giờ có nhiều hơn một phần tử (vì mỗi node có tối đa một con). DFS cần call stack sâu 10^4 frame. Nếu bạn quan tâm đến worst-case behavior trong constraints cho trước, BFS thắng.

Giá trị âm. -1000 serialize thành "-1000". Delimiter dấu phẩy không va chạm với dấu trừ. Parse với int() hoặc int.Parse() xử lý đúng dấu âm. Không cần xử lý đặc biệt.

Giá trị trông giống null marker. Null marker của bạn ("null" hoặc "#") không được là số nguyên hợp lệ. Cả hai lựa chọn đều an toàn: không có số nguyên nào serialize thành "null" hay "#".

Trailing nulls trong BFS. Bước trim trong BFS serializer là tối ưu hóa, không phải yêu cầu correctness. Deserializer vẫn hoạt động đúng nếu trailing nulls còn đó, vì điều kiện vòng lặp i < len(values) ngăn overrun. Trim giữ cho string encode ngắn hơn.

So sánh

Cả hai tuyến tính. Space cho encoded string là O(N) trong cả hai trường hợp: BFS ghi tối đa 2N-1 token trước khi trim, DFS ghi đúng 2N+1 token (N giá trị cộng N+1 null marker cho full binary tree). Trong thực tế string BFS sau trim ngắn hơn với cây thưa; string DFS có thể dài hơn vì nó đánh dấu null children của mọi lá.

Nên ship cái nào

Tôi sẽ ship phiên bản DFS preorder cho interview và cho hầu hết use case thực tế, kèm ghi chú về recursion depth. Lý do là sự đối xứng giữa encode và decode: preorder serializer và iterator-driven deserializer có cấu trúc giống hệt nhau -- một cái ghi, một cái đọc, cả hai theo cùng thứ tự duyệt. Điều đó làm cho cặp này dễ lý luận và dễ kiểm tra tính đúng đắn. Phiên bản BFS đòi hỏi bạn suy nghĩ về cách queue trong deserializer phản chiếu queue trong serializer, và index bookkeeping là nguồn gốc của lỗi off-by-one khi làm bài dưới áp lực.

Tình huống duy nhất tôi chọn BFS đầu tiên là khi bài toán đề cập rõ ràng đến cây rất sâu hoặc khi stack depth là ràng buộc được nêu. 10^4 node trong cây lệch là sát giới hạn Python. Nếu bài nói 10^5 hay 10^6, BFS không còn là tùy chọn nữa.

Pattern nền tảng và nơi nó xuất hiện

Design insight ở đây là structural encoding: bạn không thể encode một cây chỉ từ giá trị vì cùng một multiset giá trị có thể mô tả nhiều cây khác nhau. Bạn cần hoặc tín hiệu cấu trúc rõ ràng (null markers, như trong DFS preorder) hoặc thứ tự duyệt tự phân định ranh giới (level-order với positional queue). Cả hai chiến lược xuất hiện trong mọi bài toán serialization -- không chỉ cây.

Cùng pattern này xuất hiện trong các bài láng giềng của series trees:

Serialize and Deserialize BST (449) thêm thuộc tính BST: con trái nhỏ hơn, con phải lớn hơn. Constraint đó làm null marker trở thành không cần thiết -- bạn có thể tái tạo cây chỉ từ giá trị preorder bằng cách biết ranh giới chia left/right subtree phải ở đâu. Encoding ngắn hơn nhưng decode phức tạp hơn.

Serialize and Deserialize N-ary Tree (428) mở rộng thiết kế cho cây trong đó mỗi node có thể có bất kỳ số lượng con nào. Cách tiếp cận preorder khái quát hóa bằng cách encode số lượng con tại mỗi node. Cùng structural-encoding insight; chỉ cần thêm thông tin mỗi node.

Find Duplicate Subtrees (652) dùng serialization như một công cụ chứ không phải mục tiêu. Bạn serialize mỗi subtree thành canonical string và dùng hash map để phát hiện trùng lặp. DFS preorder encoding với null markers hoạt động trực tiếp như canonical form.

Construct Binary Tree from Preorder and Inorder Traversal (105) là bài nghịch đảo: cho hai chuỗi duyệt (không có null marker), tái tạo cây. Nó cho thấy tại sao preorder một mình không đủ nếu không có structural marker -- bạn cần inorder để biết subtree trái kết thúc ở đâu. Encoding preorder-với-nulls của bài 297 tránh sự mơ hồ này bằng cách làm cấu trúc trở thành tường minh.