题解 | 序列化二叉树

1、解题思路

1. 层序遍历（BFS）序列化：使用队列进行层序遍历。节点值之间用逗号分隔，空节点用 # 表示。
2. 层序遍历反序列化：将字符串按逗号分割成节点列表。使用队列重建二叉树，依次处理每个节点。

2、代码实现

C++

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};
*/
#include <sstream>
#include <string>
#include <vector>
class Solution {
  public:
    char* Serialize(TreeNode* root) {
        if (root == nullptr) {
            return "#";
        }

        queue<TreeNode*> q;
        q.push(root);
        string result;

        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            if (node == nullptr) {
                result += "#,";
            } else {
                result += to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            }
        }

        // Remove trailing comma
        if (!result.empty() && result.back() == ',') {
            result.pop_back();
        }

        // Convert string to char*
        char* buffer = new char[result.size() + 1];
        strcpy(buffer, result.c_str());
        return buffer;
    }
    TreeNode* Deserialize(char* str) {
        if (str == nullptr || str[0] == '#') {
            return nullptr;
        }

        string data(str);
        vector<string> nodes;
        stringstream ss(data);
        string item;

        while (getline(ss, item, ',')) {
            nodes.push_back((item));
        }

        if (nodes.empty()) {
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(nodes[0]));
        queue<TreeNode*> q;
        q.push(root);

        int index = 1;
        while (!q.empty() && index < nodes.size()) {
            TreeNode* node = q.front();
            q.pop();

            // Left child
            if (nodes[index] != "#") {
                node->left = new TreeNode(stoi(nodes[index]));
                q.push(node->left);
            }
            index++;

            // Right child
            if (index < nodes.size() && nodes[index] != "#") {
                node->right = new TreeNode(stoi(nodes[index]));
                q.push(node->right);
            }
            index++;
        }

        return root;
    }
};

Java

import java.util.*;
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    String Serialize(TreeNode root) {
        if (root == null) return "#";

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        StringBuilder sb = new StringBuilder();

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node == null) {
                sb.append("#,");
            } else {
                sb.append(node.val).append(",");
                queue.add(node.left);
                queue.add(node.right);
            }
        }

        // Remove trailing comma
        if (sb.charAt(sb.length() - 1) == ',') {
            sb.deleteCharAt(sb.length() - 1);
        }

        return sb.toString();
    }
    TreeNode Deserialize(String str) {
        if (str.equals("#")) return null;

        String[] nodes = str.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int index = 1;
        while (!queue.isEmpty() && index < nodes.length) {
            TreeNode node = queue.poll();

            // Left child
            if (!nodes[index].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(nodes[index]));
                queue.add(node.left);
            }
            index++;

            // Right child
            if (index < nodes.length && !nodes[index].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(nodes[index]));
                queue.add(node.right);
            }
            index++;
        }

        return root;
    }
}

Python

# -*- coding:utf-8 -*-
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class Solution:
    def Serialize(self, root):
        # write code here
        if not root:
            return "#"
        
        queue = [root]
        result = []
        
        while queue:
            node = queue.pop(0)
            
            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append("#")
        
        return ",".join(result)

    def Deserialize(self, s):
        # write code here
        if s == "#":
            return None
        
        nodes = s.split(",")
        root = TreeNode(int(nodes[0]))
        queue = [root]
        
        index = 1
        while queue and index < len(nodes):
            node = queue.pop(0)
            
            # Left child
            if nodes[index] != "#":
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1
            
            # Right child
            if index < len(nodes) and nodes[index] != "#":
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1
        
        return root

3、复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，存储节点队列和字符串。