LeetCode 剑指 Offer 37. 序列化二叉树

Categories:

题目描述
思路分析
1. 解法一：前序遍历 + 空节点占位（推荐）
相似题目

题目描述

✅ 剑指 Offer 37. 序列化二叉树

思路分析

解法一：前序遍历 + 空节点占位（推荐）

核心思路：

前序遍历输出节点值，空节点使用 # 占位并以逗号分隔。

反序列化时按序读取，遇到 # 返回空节点，否则创建节点并递归构建左右子树。

该格式可以唯一还原原树结构。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数量。

空间复杂度：O(n)，递归栈与序列化字符串。

public class Codec {
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }

        sb.append(node.val).append(',');
        buildString(node.left, sb);
        buildString(node.right, sb);
    }

    public TreeNode deserialize(String data) {
        String[] parts = data.split(",");
        int[] idx = new int[1];
        return buildTree(parts, idx);
    }

    private TreeNode buildTree(String[] parts, int[] idx) {
        if (idx[0] >= parts.length) {
            return null;
        }

        String val = parts[idx[0]++];
        if (val.equals("#") || val.isEmpty()) {
            return null;
        }

        TreeNode node = new TreeNode(Integer.parseInt(val));
        node.left = buildTree(parts, idx);
        node.right = buildTree(parts, idx);
        return node;
    }
}

import (
	"strconv"
	"strings"
)

type Codec struct{}

func Constructor() Codec {
	return Codec{}
}

func (c *Codec) serialize(root *TreeNode) string {
	var sb strings.Builder
	buildString(root, &sb)
	return sb.String()
}

func buildString(node *TreeNode, sb *strings.Builder) {
	if node == nil {
		sb.WriteString("#,")
		return
	}

	sb.WriteString(strconv.Itoa(node.Val))
	sb.WriteString(",")
	buildString(node.Left, sb)
	buildString(node.Right, sb)
}

func (c *Codec) deserialize(data string) *TreeNode {
	parts := strings.Split(data, ",")
	idx := 0
	return buildTree(parts, &idx)
}

func buildTree(parts []string, idx *int) *TreeNode {
	if *idx >= len(parts) {
		return nil
	}

	val := parts[*idx]
	*idx = *idx + 1

	if val == "#" || val == "" {
		return nil
	}

	num, _ := strconv.Atoi(val)
	node := &TreeNode{Val: num}
	node.Left = buildTree(parts, idx)
	node.Right = buildTree(parts, idx)
	return node
}

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	序列化
449. 序列化和反序列化二叉搜索树	中等	序列化
102. 二叉树的层序遍历	中等	BFS
105. 从前序与中序遍历序列构造二叉树	中等	递归
226. 翻转二叉树	简单	递归

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/91810127