LeetCode LCR 048. 二叉树的序列化与反序列化

Categories:

题目描述
思路分析
1. 解法一：BFS 层序遍历（推荐）
2. 解法二：DFS 前序遍历
相似题目

题目描述

✅ LCR 048. 二叉树的序列化与反序列化

思路分析

解法一：BFS 层序遍历（推荐）

核心思路：

序列化：使用队列进行层序遍历，将节点值逐一追加到结果中，空节点用 "#" 占位，各值以逗号分隔。非空节点的左右子节点（含空节点）均入队，保证位置信息完整。

反序列化：按逗号拆分字符串，取首元素建根节点并入队，维护 index 指针。每次从队列弹出父节点，依次读取 index 处的值构建左子节点和右子节点，非空节点入队继续处理。

BFS 生成的序列化结果与 LeetCode 官方格式一致，直观易调试。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树节点数，每个节点恰好访问一次

空间复杂度：O(n)，队列及结果字符串均最多存储 n 个节点信息

public class Codec {

    // 序列化：BFS 层序遍历，空节点用 "#" 占位
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,");
            } else {
                sb.append(node.val).append(",");
                // 左右子节点均入队（含空节点，保证位置完整）
                queue.offer(node.left);
                queue.offer(node.right);
            }
        }
        return sb.toString();
    }

    // 反序列化：按逗号分割后用队列还原父子关系
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] vals = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i = 1;
        while (!queue.isEmpty() && i < vals.length) {
            TreeNode node = queue.poll();
            // 构建左子节点
            if (!vals[i].equals("#")) {
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.left);
            }
            i++;
            // 构建右子节点
            if (i < vals.length && !vals[i].equals("#")) {
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

type Codec struct{}

func Constructor() Codec { return Codec{} }

// 序列化：BFS 层序遍历，空节点用 "#" 占位，逗号分隔
func (c *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    var res []string
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        if node == nil {
            res = append(res, "#")
        } else {
            res = append(res, strconv.Itoa(node.Val))
            // 左右子节点均入队（含空节点，保证位置完整）
            queue = append(queue, node.Left, node.Right)
        }
    }
    return strings.Join(res, ",")
}

// 反序列化：按逗号分割后用队列依次还原父子关系
func (c *Codec) deserialize(data string) *TreeNode {
    if data == "" {
        return nil
    }
    vals := strings.Split(data, ",")
    root := &TreeNode{Val: mustAtoi(vals[0])}
    queue := []*TreeNode{root}
    i := 1
    for len(queue) > 0 && i < len(vals) {
        node := queue[0]
        queue = queue[1:]
        // 构建左子节点
        if vals[i] != "#" {
            node.Left = &TreeNode{Val: mustAtoi(vals[i])}
            queue = append(queue, node.Left)
        }
        i++
        // 构建右子节点
        if i < len(vals) && vals[i] != "#" {
            node.Right = &TreeNode{Val: mustAtoi(vals[i])}
            queue = append(queue, node.Right)
        }
        i++
    }
    return root
}

func mustAtoi(s string) int {
    n, _ := strconv.Atoi(s)
    return n
}

解法二：DFS 前序遍历

核心思路：

序列化：前序（根-左-右）递归遍历，空节点记录为 "#"，各值以逗号分隔拼接成字符串。

反序列化：将字符串按逗号拆分为列表，用索引指针顺序读取。遇到 "#" 返回 nil，否则建立当前节点，递归构造左子树再构造右子树，前序的构造顺序与序列化完全对应。

DFS 实现更简洁，递归逻辑直观，但递归深度在极端不平衡树时为 O(n)。

复杂度分析：

时间复杂度：O(n)，其中 n 为二叉树节点数，每个节点恰好访问一次

空间复杂度：O(n)，递归调用栈及结果列表均最多占用 O(n) 空间

public class Codec {

    // 序列化：前序递归，空节点用 "#" 占位
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        dfsSerialize(root, sb);
        return sb.toString();
    }

    private void dfsSerialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        // 先记录根节点，再递归左右子树
        sb.append(node.val).append(",");
        dfsSerialize(node.left, sb);
        dfsSerialize(node.right, sb);
    }

    // 反序列化：用索引指针按前序顺序依次读取并还原
    public TreeNode deserialize(String data) {
        String[] vals = data.split(",");
        int[] index = {0};
        return dfsDeserialize(vals, index);
    }

    private TreeNode dfsDeserialize(String[] vals, int[] index) {
        if (vals[index[0]].equals("#")) {
            index[0]++;
            return null;
        }
        // 建立当前节点，递归构造左子树再构造右子树
        TreeNode node = new TreeNode(Integer.parseInt(vals[index[0]++]));
        node.left = dfsDeserialize(vals, index);
        node.right = dfsDeserialize(vals, index);
        return node;
    }
}

type Codec struct{}

func Constructor() Codec { return Codec{} }

// 序列化：前序递归，空节点用 "#" 占位，逗号分隔
func (c *Codec) serialize(root *TreeNode) string {
    var sb strings.Builder
    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            sb.WriteString("#,")
            return
        }
        // 先记录根节点，再递归左右子树
        sb.WriteString(strconv.Itoa(node.Val))
        sb.WriteByte(',')
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return sb.String()
}

// 反序列化：用索引指针按前序顺序依次读取并还原
func (c *Codec) deserialize(data string) *TreeNode {
    vals := strings.Split(data, ",")
    idx := 0
    var dfs func() *TreeNode
    dfs = func() *TreeNode {
        if idx >= len(vals) || vals[idx] == "#" {
            idx++
            return nil
        }
        // 建立当前节点，递归构造左子树再构造右子树
        val, _ := strconv.Atoi(vals[idx])
        idx++
        node := &TreeNode{Val: val}
        node.Left = dfs()
        node.Right = dfs()
        return node
    }
    return dfs()
}

相似题目

题目	难度	考察点
449. 序列化和反序列化二叉搜索树	中等	BFS/DFS 序列化、BST 性质
428. 序列化和反序列化 N 叉树	困难	BFS/DFS 序列化、N 叉树
271. 字符串的编码与解码	中等	字符串编解码设计
105. 从前序与中序遍历序列构造二叉树	中等	递归重建二叉树
106. 从中序与后序遍历序列构造二叉树	中等	递归重建二叉树
652. 寻找重复的子树	中等	序列化子树 + 哈希
331. 验证二叉树的前序序列化	中等	前序序列合法性验证

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/94009103