LeetCode 428. 序列化和反序列化 N 叉树

Categories:

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

题目描述

✅ 428. 序列化和反序列化 N 叉树

思路分析

解法一：前序遍历 + 子节点数量（推荐）

核心思路：

序列化时对每个节点记录 值 与 子节点数量，然后递归处理子节点。

反序列化时按同样顺序读取，先建节点，再递归构建子树。

复杂度分析：

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

空间复杂度：O(n)，用于递归栈与序列化结果。

import java.util.ArrayList;
import java.util.List;

class Codec {
    public String serialize(Node root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        serializeDfs(root, sb);
        sb.setLength(sb.length() - 1);
        return sb.toString();
    }

    private void serializeDfs(Node node, StringBuilder sb) {
        if (node == null) {
            return;
        }
        sb.append(node.val).append(',').append(node.children.size()).append(',');
        for (Node child : node.children) {
            serializeDfs(child, sb);
        }
    }

    public Node deserialize(String data) {
        if (data == null || data.isEmpty()) {
            return null;
        }
        String[] parts = data.split(",");
        int[] idx = {0};
        return deserializeDfs(parts, idx);
    }

    private Node deserializeDfs(String[] parts, int[] idx) {
        int val = Integer.parseInt(parts[idx[0]++]);
        int size = Integer.parseInt(parts[idx[0]++]);

        Node node = new Node(val, new ArrayList<>());
        for (int i = 0; i < size; i++) {
            node.children.add(deserializeDfs(parts, idx));
        }
        return node;
    }
}

import (
	"strconv"
	"strings"
)

type Codec struct{}

func (c *Codec) serialize(root *Node) string {
	if root == nil {
		return ""
	}
	var sb strings.Builder
	serializeNary(root, &sb)
	res := sb.String()
	return res[:len(res)-1]
}

func serializeNary(node *Node, sb *strings.Builder) {
	if node == nil {
		return
	}
	sb.WriteString(strconv.Itoa(node.Val))
	sb.WriteByte(',')
	sb.WriteString(strconv.Itoa(len(node.Children)))
	sb.WriteByte(',')
	for _, child := range node.Children {
		serializeNary(child, sb)
	}
}

func (c *Codec) deserialize(data string) *Node {
	if data == "" {
		return nil
	}
	parts := strings.Split(data, ",")
	idx := 0
	return deserializeNary(parts, &idx)
}

func deserializeNary(parts []string, idx *int) *Node {
	val, _ := strconv.Atoi(parts[*idx])
	*idx += 1
	size, _ := strconv.Atoi(parts[*idx])
	*idx += 1

	node := &Node{Val: val, Children: []*Node{}}
	for i := 0; i < size; i++ {
		node.Children = append(node.Children, deserializeNary(parts, idx))
	}
	return node
}

相似题目

题目	难度	考察点
428. 序列化和反序列化 N 叉树	困难	递归
297. 二叉树的序列化与反序列化	困难	递归
449. 序列化和反序列化二叉搜索树	中等	递归
589. N 叉树的前序遍历	简单	递归
590. N 叉树的后序遍历	简单	递归
102. 二叉树的层序遍历	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/72860504