东哥带你刷二叉树（序列化篇）

labuladong约 5625 字大约 19 分钟数据结构二叉树分解问题的思路层级遍历

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
297. Serialize and Deserialize Binary Treeopen in new window	297. 二叉树的序列化与反序列化open in new window	🔴
-	剑指 Offer 37. 序列化二叉树open in new window	🔴
-	剑指 Offer II 048. 序列化与反序列化二叉树open in new window	🔴

Info

在开头先打个广告，我的手把手刷二叉树课程open in new window 按照公式和套路讲解了 150 道二叉树题目，只需一顿饭钱，就能手把手带你刷完二叉树分类的题目，迅速掌握递归思维，让你豁然开朗。我绝对有这个信心，信不信，可以等你看完我的二叉树算法系列文章再做评判。

本文是承接东哥带你刷二叉树（纲领篇）的第三篇文章，前文东哥带你刷二叉树（构造篇）带你学习了二叉树构造技巧，本文加大难度，让你对二叉树同时进行「序列化」和「反序列化」。

要说序列化和反序列化，得先从 JSON 数据格式说起。

JSON 的运用非常广泛，比如我们经常将变成语言中的结构体序列化成 JSON 字符串，存入缓存或者通过网络发送给远端服务，消费者接受 JSON 字符串然后进行反序列化，就可以得到原始数据了。

这就是序列化和反序列化的目的，以某种特定格式组织数据，使得数据可以独立于编程语言。

那么假设现在有一棵用 Java 实现的二叉树，我想把它通过某些方式存储下来，然后用 C++ 读取这棵并还原这棵二叉树的结构，怎么办？这就需要对二叉树进行序列化和反序列化了。

零、前/中/后序和二叉树的唯一性

谈具体的题目之前，我们先思考一个问题：什么样的序列化的数据可以反序列化出唯一的一棵二叉树？

比如说，如果给你一棵二叉树的前序遍历结果，你是否能够根据这个结果还原出这棵二叉树呢？

答案是也许可以，也许不可以，具体要看你给的前序遍历结果是否包含空指针的信息。如果包含了空指针，那么就可以唯一确定一棵二叉树，否则就不行。

举例来说，如果我给你这样一个不包含空指针的前序遍历结果 [1,2,3,4,5]，那么如下两棵二叉树都是满足这个前序遍历结果的：

所以给定不包含空指针信息的前序遍历结果，是不能还原出唯一的一棵二叉树的。

但如果我的前序遍历结果包含空指针的信息，那么就能还原出唯一的一棵二叉树了。比如说用 # 表示空指针，上图左侧的二叉树的前序遍历结果就是 [1,2,3,#,#,4,#,#,5,#,#]，上图右侧的二叉树的前序遍历结果就是 [1,2,#,3,#,#,4,5,#,#,#]，它俩就区分开了。

那么估计就有聪明的小伙伴说了：东哥我懂了，甭管是前中后序哪一种遍历顺序，只要序列化的结果中包含了空指针的信息，就能还原出唯一的一棵二叉树了。

首先要夸一下这种举一反三的思维，但很不幸，正确答案是，即便你包含了空指针的信息，也只有前序和后序的遍历结果才能唯一还原二叉树，中序遍历结果做不到。

本文后面会具体探讨这个问题，这里只简单说下原因：因为前序/后序遍历的结果中，可以确定根节点的位置，而中序遍历的结果中，根节点的位置是无法确定的。

更直观的，比如如下两棵二叉树显然拥有不同的结构，但它俩的中序遍历结果都是 [#,1,#,1,#]，无法区分：

说了这么多，总结下结论，当二叉树中节点的值不存在重复时：

如果你的序列化结果中不包含空指针的信息，且你只给出一种遍历顺序，那么你无法还原出唯一的一棵二叉树。
如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文东哥手把手带你刷二叉树（构造篇）所说，分两种情况：
2.1. 如果你给出的是前序和中序，或者后序和中序，那么你可以还原出唯一的一棵二叉树。
2.2. 如果你给出前序和后序，那么你无法还原出唯一的一棵二叉树。
如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
3.1. 如果你给出的是前序或者后序，那么你可以还原出唯一的一棵二叉树。
3.2. 如果你给出的是中序，那么你无法还原出唯一的一棵二叉树。

我在开头提一下这些总结性的认识，可以理解性记忆，之后会遇到一些相关的题目，再回过头来看看这些总结，会有更深的理解，下面看具体的题目吧。

一、题目描述

力扣第 297 题「二叉树的序列化与反序列化open in new window」就是给你输入一棵二叉树的根节点 root，要求你实现如下一个类：

public class Codec {

    // 把一棵二叉树序列化成字符串
    public String serialize(TreeNode root) {}

    // 把字符串反序列化成二叉树
    public TreeNode deserialize(String data) {}
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Codec {
public:
    // 把一棵二叉树序列化成字符串
    string serialize(TreeNode* root);

    // 把字符串反序列化成二叉树
    TreeNode* deserialize(string data);
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

class Codec:
    
    # 把一棵二叉树序列化成字符串
    def serialize(self, root: TreeNode) -> str:
        pass

    # 把字符串反序列化成二叉树
    def deserialize(self, data: str) -> TreeNode:
        pass

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

type Codec struct{}

// 把一棵二叉树序列化成字符串
func (codec *Codec) serialize(root *TreeNode) string {}

// 把字符串反序列化成二叉树
func (codec *Codec) deserialize(data string) *TreeNode {}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var Codec = function () {
    
    // 把一棵二叉树序列化成字符串
    this.serialize = function (root) {}
    
    // 把字符串反序列化成二叉树
    this.deserialize = function (data) {}
};

我们可以用 serialize 方法将二叉树序列化成字符串，用 deserialize 方法将序列化的字符串反序列化成二叉树，至于以什么格式序列化和反序列化，这个完全由你决定。

比如说输入如下这样一棵二叉树：

serialize 方法也许会把它序列化成字符串 2,1,#,6,#,#,3,#,#，其中 # 表示 null 指针，那么把这个字符串再输入 deserialize 方法，依然可以还原出这棵二叉树。

也就是说，这两个方法会成对儿使用，你只要保证他俩能够自洽就行了。

想象一下，二叉树结该是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化不过就是把结构化的数据「打平」，本质就是在考察二叉树的遍历方式。

二叉树的遍历方式有哪些？递归遍历方式有前序遍历，中序遍历，后序遍历；迭代方式一般是层级遍历。本文就把这些方式都尝试一遍，来实现 serialize 方法和 deserialize 方法。

二、前序遍历解法

前文学习数据结构和算法的框架思维说过了二叉树的几种遍历方式，前序遍历框架如下：

void traverse(TreeNode root) {
    if (root == null) return;

    // 前序位置的代码
    traverse(root.left);
    traverse(root.right);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

void traverse(TreeNode* root) {
    if (root == nullptr) return;

    // 前序位置的代码
    traverse(root->left);
    traverse(root->right);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

def traverse(root):
    if root is None:
        return
    # 前序位置的代码
    traverse(root.left)
    traverse(root.right)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func traverse(root *TreeNode) {
    if root == nil {
        return
    }

    // 前序位置的代码
    traverse(root.left)
    traverse(root.right)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var traverse = function(root) {
  if (root == null) return;
  traverse(root.left); // 前序位置的代码
  traverse(root.right);
};

真的很简单，在递归遍历两棵子树之前写的代码就是前序遍历代码，那么请你看一看如下伪码：

LinkedList<Integer> res;
void traverse(TreeNode root) {
    if (root == null) {
        // 暂且用数字 -1 代表空指针 null
        res.addLast(-1);
        return;
    }

    /****** 前序位置 ******/
    res.addLast(root.val);
    /***********************/

    traverse(root.left);
    traverse(root.right);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

list<int> res;
void traverse(TreeNode* root) {
    if (root == nullptr) {
        // 暂且用数字 -1 代表空指针 null
        res.push_back(-1);
        return;
    }

    /****** 前序位置 ******/
    res.push_back(root->val);
    /***********************/

    traverse(root->left);
    traverse(root->right);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

from typing import List

res: List[int]
def traverse(root: TreeNode) -> None:
    if root is None:
        # 暂且用数字 -1 代表空指针 null
        res.append(-1)
        return

    /****** 前序位置 ******/
    res.append(root.val)
    /***********************/

    traverse(root.left)
    traverse(root.right)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var res *list.List

func traverse(root *TreeNode) {
    if root == nil {
        // 暂且用数字 -1 代表空指针 null
        res.PushBack(-1)
        return
    }

    /****** 前序位置 ******/
    res.PushBack(root.Val)
    /***********************/

    traverse(root.Left)
    traverse(root.Right)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var res;
function traverse(root) {
  if (root == null) {
    // 暂且用数字 -1 代表空指针 null
    res.addLast(-1);
    return;
  }

  /****** 前序位置 ******/
  res.addLast(root.val);
  /***********************/

  traverse(root.left);
  traverse(root.right);
}

调用 traverse 函数之后，你是否可以立即想出这个 res 列表中元素的顺序是怎样的？比如如下二叉树（# 代表空指针 null），可以直观看出前序遍历做的事情：

那么 res = [1,2,-1,4,-1,-1,3,-1,-1]，这就是将二叉树「打平」到了一个列表中，其中 -1 代表 null。

那么，将二叉树打平到一个字符串中也是完全一样的：

// 代表分隔符的字符
String SEP = ",";
// 代表 null 空指针的字符
String NULL = "#";
// 用于拼接字符串
StringBuilder sb = new StringBuilder();

/* 将二叉树打平为字符串 */
void traverse(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append(NULL).append(SEP);
        return;
    }

    /****** 前序位置 ******/
    sb.append(root.val).append(SEP);
    /***********************/

    traverse(root.left, sb);
    traverse(root.right, sb);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

#include <string>
#include <iostream>
using namespace std;

// 代表分隔符的字符
string SEP = ",";
// 代表 null 空指针的字符
string NULL = "#";
// 用于拼接字符串
stringstream ss;

/* 将二叉树打平为字符串 */
void traverse(TreeNode* root, stringstream& ss) {
    if (root == NULL) {
        ss << NULL << SEP;
        return;
    }

    /****** 前序位置 ******/
    ss << root->val << SEP;
    /***********************/

    traverse(root->left, ss);
    traverse(root->right, ss);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 代表分隔符的字符
SEP = ","
# 代表 null 空指针的字符
NULL = "#"
# 用于拼接字符串
sb = []

# 将二叉树打平为字符串
def traverse(root: TreeNode, sb: List[str]):
    if not root:
        sb.append(NULL)
        sb.append(SEP)
        return

    /****** 前序位置 ******/
    sb.append(str(root.val))
    sb.append(SEP)
    /***********************/

    traverse(root.left, sb)
    traverse(root.right, sb)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 代表分隔符的字符
const SEP = ","
// 代表null空指针的字符
const NULL = "#"
// 用于拼接字符串
var sb strings.Builder

/* 将二叉树打平为字符串 */
func traverse(root *TreeNode, sb *strings.Builder) {
    if root == nil {
        sb.WriteString(NULL)
        sb.WriteString(SEP)
        return
    }

    /****** 前序位置 ******/
    sb.WriteString(strconv.Itoa(root.Val))
    sb.WriteString(SEP)
    /***********************/

    traverse(root.Left, sb)
    traverse(root.Right, sb)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 代表分隔符的字符
var SEP = ",";
// 代表 null 空指针的字符
var NULL = "#";
// 用于拼接字符串
var sb = new StringBuilder();

/* 将二叉树打平为字符串 */
function traverse(root, sb) {
    if (root == null) {
        sb.append(NULL).append(SEP);
        return;
    }

    /****** 前序位置 ******/
    sb.append(root.val).append(SEP);
    /***********************/

    traverse(root.left, sb);
    traverse(root.right, sb);
}

StringBuilder 可以用于高效拼接字符串，所以也可以认为是一个列表，用 , 作为分隔符，用 # 表示空指针 null，调用完 traverse 函数后，sb 中的字符串应该是 1,2,#,4,#,#,3,#,#,。

至此，我们已经可以写出序列化函数 serialize 的代码了：

String SEP = ",";
String NULL = "#";

/* 主函数，将二叉树序列化为字符串 */
String serialize(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    serialize(root, sb);
    return sb.toString();
}

/* 辅助函数，将二叉树存入 StringBuilder */
void serialize(TreeNode root, StringBuilder sb) {
    if (root == null) {
        sb.append(NULL).append(SEP);
        return;
    }

    /****** 前序位置 ******/
    sb.append(root.val).append(SEP);/**<extend up -200><div class="img-content"><img src="/algo/images/二叉树序列化/1.jpeg" class="myimage"/></div> */
    /***********************/

    serialize(root.left, sb);
    serialize(root.right, sb);
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

string SEP = ",";
string NULL = "#";

/* 主函数，将二叉树序列化为字符串 */
string serialize(TreeNode* root) {
    string str;
    serialize(root, str);
    return str;
}

/* 辅助函数，将二叉树存入 string */
void serialize(TreeNode* root, string& str) {
    if (root == NULL) {
        str += NULL + SEP;
        return;
    }

    /* 前序位置 */
    str += to_string(root->val) + SEP;

    serialize(root->left, str);
    serialize(root->right, str);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

SEP = ","
NULL = "#"

def serialize(root: TreeNode) -> str:
    sb = StringBuilder()
    serialize_helper(root, sb)
    return sb.toString()

def serialize_helper(root: TreeNode, sb: StringBuilder):
    if root is None:
        sb.append(NULL).append(SEP)
        return
    
    #前序位置
    sb.append(root.val).append(SEP) # <extend up -200><div class="img-content"><img src="/algo/images/二叉树序列化/1.jpeg" class="myimage"/></div> #
    serialize_helper(root.left, sb)
    serialize_helper(root.right, sb)

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var SEP string = ","
var NULL string = "#"

// 主函数，将二叉树序列化为字符串
func serialize(root *TreeNode) string {
    sb := new(strings.Builder)
    serialize_helper(root, sb)
    return sb.String()
}

// 辅助函数，将二叉树存入 StringBuilder
func serialize_helper(root *TreeNode, sb *strings.Builder) {
    if root == nil {
        sb.WriteString(NULL)
        sb.WriteString(SEP)
        return
    }

    /****** 前序位置 ******/
    sb.WriteString(strconv.Itoa(root.Val))
    sb.WriteString(SEP)/**<extend up -200><div class="img-content"><img src="/algo/images/二叉树序列化/1.jpeg" class="myimage"/></div> */
    /***********************/

    serialize_helper(root.Left, sb)
    serialize_helper(root.Right, sb)
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var SEP = ",";
var NULL = "#";

/* 主函数，将二叉树序列化为字符串 */
function serialize(root) {
    var sb = "";
    serializeHelper(root, sb);
    return sb.toString();
}

/* 辅助函数，将二叉树存入字符串 */
function serializeHelper(root, sb) {
    if (root == null) {
        sb += NULL + SEP;
        return;
    }

    /* 前序位置 */
    sb += root.val + SEP;
    /* extend up -200
    <div class="img-content"><img src="/images/二叉树序列化/1.jpeg" class="myimage"/></div>
    */

    serializeHelper(root.left, sb);
    serializeHelper(root.right, sb);
}

现在，思考一下如何写 deserialize 函数，将字符串反过来构造二叉树。

首先我们可以把字符串转化成列表：

String data = "1,2,#,4,#,#,3,#,#,";
String[] nodes = data.split(",");

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

string data = "1,2,#,4,#,#,3,#,#,";
vector<string> nodes;
stringstream ss(data);
string item;
while(getline(ss, item, ',')) {
    nodes.push_back(item);
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

data = "1,2,#,4,#,#,3,#,#,"
nodes = data.split(",")

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

data := "1,2,#,4,#,#,3,#,#,"
nodes := strings.Split(data, ",")

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var data = "1,2,#,4,#,#,3,#,#,";
var nodes = data.split(",");

这样，nodes 列表就是二叉树的前序遍历结果，问题转化为：如何通过二叉树的前序遍历结果还原一棵二叉树？

Tip

前文东哥带你刷二叉树（构造篇）说过，至少要得到前、中、后序遍历中的两种互相配合才能还原二叉树。那是因为前文的遍历结果没有记录空指针的信息。这里的 nodes 列表包含了空指针的信息，所以只使用 nodes 列表就可以还原二叉树。

根据我们刚才的分析，nodes 列表就是一棵打平的二叉树：

那么，反序列化过程也是一样，先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树即可：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 零、前/中/后序和二叉树的唯一性

# 一、题目描述

# 二、前序遍历解法

零、前/中/后序和二叉树的唯一性

一、题目描述

二、前序遍历解法