二叉树心法（序列化篇）
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 297. Serialize and Deserialize Binary Tree | 🔴 |
Prerequisites
Before reading this article, you should first learn:
This article is the third part following Dong Ge's Guide to Binary Trees (Overview). The previous article, Dong Ge's Guide to Binary Trees (Construction), taught you binary tree construction techniques. This article increases the difficulty by teaching you both "serialization" and "deserialization" of binary trees.
To understand serialization and deserialization, we must first talk about the JSON data format.
JSON is widely used. For example, we often serialize structures from programming languages into JSON strings, store them in caches, or send them over the network to remote services. The receiver then deserializes the JSON string to retrieve the original data.
The purpose of serialization and deserialization is to organize data in a specific format, making it independent of the programming language.
Now, let's assume we have a binary tree implemented in Java, and we want to store it and later read and reconstruct this binary tree structure using C++. How can we do that? This requires the serialization and deserialization of the binary tree.
0. Preorder, Inorder, Postorder and the Uniqueness of Binary Trees
Before we talk about specific problems, let's think about a question: What kind of serialized data can be deserialized into a unique binary tree?
For example, if you are given the preorder traversal result of a binary tree, can you reconstruct the binary tree from this result?
The answer is maybe yes, maybe no. It depends on whether the preorder traversal result includes information about null pointers. If null pointers are included, then you can uniquely determine a binary tree. Otherwise, you cannot.
For instance, if I give you a preorder traversal result [1,2,3,4,5] that does not include null pointers, both of the following binary trees satisfy this preorder traversal result:
So, given a preorder traversal result without null pointers, you cannot reconstruct a unique binary tree.
However, if the preorder traversal result includes null pointer information, you can reconstruct a unique binary tree. For example, using # to represent null pointers, the preorder traversal result of the left binary tree is [1,2,3,#,#,4,#,#,5,#,#], and the preorder traversal result of the right binary tree is [1,2,#,3,#,#,4,5,#,#,#], clearly distinguishing the two.
Some smart readers might say: "I get it! Regardless of whether it's preorder, inorder, or postorder traversal, as long as the serialized result includes null pointer information, you can uniquely reconstruct a binary tree."
While this is a commendable way of thinking, the correct answer is that even if you include null pointer information, only preorder and postorder traversal results can uniquely reconstruct a binary tree; inorder traversal results cannot.
We will explore this issue in detail later, but here is a brief explanation: preorder/postorder traversal results can determine the position of the root node, whereas inorder traversal results cannot.
To illustrate, consider the following two binary trees, which clearly have different structures, but their inorder traversal results are the same [#,1,#,1,#], making them indistinguishable:
So, to summarize, when there are no duplicate values in the nodes of the binary tree:
If your serialized result does not include null pointer information and you only provide one traversal order, you cannot reconstruct a unique binary tree.
If your serialized result does not include null pointer information and you provide two traversal orders, then according to the previous article Hand-in-Hand with Dong Brother to Brush Binary Trees (Construction), there are two scenarios:
2.1. If you provide preorder and inorder, or postorder and inorder, you can reconstruct a unique binary tree.
2.2. If you provide preorder and postorder, you cannot reconstruct a unique binary tree.
If your serialized result includes null pointer information and you only provide one traversal order, there are two scenarios:
3.1. If you provide preorder or postorder, you can reconstruct a unique binary tree.
3.2. If you provide inorder, you cannot reconstruct a unique binary tree.
I mention these summary points at the beginning for easier understanding and memorization. As we encounter related problems, you can revisit these summaries for deeper comprehension. Now, let's look at specific problems.
1. Problem Description
Leetcode Problem 297 "Serialize and Deserialize Binary Tree" asks you to implement a class that, given the root node root of a binary tree, performs the following functions:
public class Codec {
// serialize a binary tree into a string
public String serialize(TreeNode root) {}
// deserialize a string into a binary tree
public TreeNode deserialize(String data) {}
}class Codec {
public:
// serialize a binary tree into a string
string serialize(TreeNode* root);
// deserialize a string into a binary tree
TreeNode* deserialize(string data);
};class Codec:
# serialize a binary tree into a string
def serialize(self, root: TreeNode) -> str:
pass
# deserialize a string into a binary tree
def deserialize(self, data: str) -> TreeNode:
passtype Codec struct{}
// serialize a binary tree into a string
func (codec *Codec) serialize(root *TreeNode) string {}
// deserialize a string into a binary tree
func (codec *Codec) deserialize(data string) *TreeNode {}var Codec = function () {
// serialize a binary tree into a string
this.serialize = function (root) {}
// deserialize a string into a binary tree
this.deserialize = function (data) {}
};We can use the serialize method to serialize a binary tree into a string and the deserialize method to deserialize the string back into a binary tree. The format for serialization and deserialization is entirely up to you.
For example, given the following binary tree:
The serialize method might serialize it into the string 2,1,#,6,#,#,3,#,#, where # represents a null pointer. If you pass this string to the deserialize method, it can reconstruct the same binary tree.
In other words, these two methods work as a pair, and you only need to ensure that they are consistent with each other.
Imagine a binary tree as a structure in a two-dimensional plane, while the serialized string is a linear one-dimensional structure. Serialization is essentially "flattening" the structured data, which is fundamentally about the traversal methods of the binary tree.
What are the traversal methods for a binary tree? Recursive traversals include preorder, inorder, and postorder traversals; iterative methods generally involve level-order traversal. This article will explore all these methods to implement the serialize and deserialize methods.
2. Preorder Traversal Solution
In the article Binary Tree Traversal Basics, we discussed various traversal methods for binary trees. The framework for preorder traversal is as follows:
void traverse(TreeNode root) {
if (root == null) return;
// code in the pre-order position
traverse(root.left);
traverse(root.right);
}void traverse(TreeNode* root) {
if (root == nullptr) return;
// code at pre-order position
traverse(root->left);
traverse(root->right);
}def traverse(root):
if root is None:
return
# code at the pre-order position
traverse(root.left)
traverse(root.right)func traverse(root *TreeNode) {
if root == nil {
return
}
// code at the pre-order position
traverse(root.left)
traverse(root.right)
}var traverse = function(root) {
if (root == null) {
return;
}
// code in the pre-order position
traverse(root.left);
traverse(root.right);
};It's really simple. The code written before recursively traversing the two subtrees is the pre-order traversal code. So, take a look at the following pseudocode:
LinkedList<Integer> res;
void traverse(TreeNode root) {
if (root == null) {
// temporarily use the number -1 to represent the null pointer
res.addLast(-1);
return;
}
// ****** pre-order position ********
res.addLast(root.val);
// ***********************
traverse(root.left);
traverse(root.right);
}list<int> res;
void traverse(TreeNode* root) {
if (root == nullptr) {
// temporarily use the number -1 to represent the null pointer
res.push_back(-1);
return;
}
// ****** pre-order position ********
res.push_back(root->val);
// ***********************
traverse(root->left);
traverse(root->right);
}res = []
def traverse(root):
if root is None:
# temporarily use the number -1 to represent the null pointer
res.append(-1)
return
# ****** pre-order position ******
res.append(root.val)
# **********************
traverse(root.left)
traverse(root.right)var res *list.List
func traverse(root *TreeNode) {
if root == nil {
// temporarily use the number -1 to represent a null pointer
res.PushBack(-1)
return
}
// ****** pre-order position ********
res.PushBack(root.Val)
// ***********************
traverse(root.Left)
traverse(root.Right)
}var res;
var traverse = function(root) {
if (root === null) {
// temporarily use the number -1 to represent the null pointer
res.push(-1);
return;
}
// ****** pre-order position ********
res.push(root.val);
// ***********************
traverse(root.left);
traverse(root.right);
}After calling the traverse function, can you immediately figure out the order of elements in the res list? For example, consider the following binary tree (# represents a null pointer). It is easy to see what preorder traversal does:
So, res = [1,2,-1,4,-1,-1,3,-1,-1]. This flattens the binary tree into a list, where -1 represents null.
Similarly, flattening the binary tree into a string follows the same process:
// character representing separator
String SEP = ",";
// character representing null pointer
String NULL = "#";
// for concatenating strings
StringBuilder sb = new StringBuilder();
// flatten the binary tree to a string
void traverse(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
// ***** pre-order position *****
sb.append(root.val).append(SEP);
// *********************
traverse(root.left, sb);
traverse(root.right, sb);
}// represents the separator character
string SEP = ",";
// represents the null pointer character
string NULL_CHAR = "#";
// used for concatenating strings
std::ostringstream os;
// flatten the binary tree into a string
void traverse(TreeNode* root, std::ostringstream& os) {
if (root == nullptr) {
os << NULL_CHAR << SEP;
return;
}
// ***** pre-order position *****
os << root->val << SEP;
// *******************
traverse(root->left, os);
traverse(root->right, os);
}# represents the separator character
SEP = ","
# represents the null pointer character
NULL = "#"
# used for concatenating strings
sb = []
# flatten the binary tree into a string
def traverse(root, sb):
if root == None:
sb.append(NULL).append(SEP)
return
# ***** pre-order position *****
sb.append(str(root.val)).append(SEP)
# *******************
traverse(root.left, sb)
traverse(root.right, sb)const (
// character representing the separator
SEP = ","
// character representing null pointer
NULL = "#"
)
func traverse(root *TreeNode, sb *strings.Builder) {
if root == nil {
sb.WriteString(NULL + SEP)
return
}
// ***** pre-order position *****
sb.WriteString(strconv.Itoa(root.Val) + SEP)
// *******************
traverse(root.Left, sb)
traverse(root.Right, sb)
}// character representing the delimiter
var SEP = ",";
// character representing null pointer
var NULL = "#";
// used for concatenating strings
var sb = "";
// flatten the binary tree into a string
var traverse = function(root) {
if (root == null) {
sb += NULL + SEP;
return;
}
// ***** pre-order position *****
sb += root.val + SEP;
// *******************
traverse(root.left);
traverse(root.right);
}StringBuilder can be used for efficient string concatenation, so you can also think of it as a list. Use , as a separator and # to represent a null pointer. After calling the traverse function, the string in sb should be 1,2,#,4,#,#,3,#,#,.
Now, we can write the code for the serialization function serialize:
class Codec {
String SEP = ",";
String NULL = "#";
// main function, serialize the binary tree to a string
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
_serialize(root, sb);
return sb.toString();
}
// helper function, store the binary tree into StringBuilder
void _serialize(TreeNode root, StringBuilder sb) {
if (root == null) {
sb.append(NULL).append(SEP);
return;
}
// ****** pre-order position ********
sb.append(root.val).append(SEP);
// ***********************
_serialize(root.left, sb);
_serialize(root.right, sb);
}
}class Codec {
public:
string SEP = ",";
string NULLSYM = "#";
string serialize(TreeNode* root) {
string sb;
_serialize(root, sb);
return sb;
}
// Helper function to serialize the binary tree into the StringBuilder
void _serialize(TreeNode* root, string& sb) {
if (root == NULL) {
sb.append(NULLSYM).append(SEP);
return;
}
// ****** Pre-order position ********
sb.append(to_string(root->val)).append(SEP);
// ************************
_serialize(root->left, sb);
_serialize(root->right, sb);
}
};class Codec:
SEP = ","
NULL = "#"
# Main function, serialize the binary tree into a string
def serialize(self, root):
sb = []
self._serialize(root, sb)
return "".join(sb)
# Helper function, store the binary tree into StringBuilder
def _serialize(self, root, sb):
if root is None:
sb.append(self.NULL)
sb.append(self.SEP)
return
# ****** Preorder position ********
sb.append(str(root.val))
sb.append(self.SEP)
# ***********************
self._serialize(root.left, sb)
self._serialize(root.right, sb)type Codec struct {
SEP string
NULL string
}
func Constructor() Codec {
return Codec{
SEP: ",",
NULL: "#",
}
}
// Main function, serialize the binary tree to a string
func (this Codec) serialize(root *TreeNode) string {
var sb strings.Builder
this._serialize(root, &sb)
return sb.String()
}
// Helper function, store the binary tree into StringBuilder
func (this Codec) _serialize(root *TreeNode, sb *strings.Builder) {
if root == nil {
sb.WriteString(this.NULL)
sb.WriteString(this.SEP)
return
}
// ****** Preorder position ********
sb.WriteString(strconv.Itoa(root.Val))
sb.WriteString(this.SEP)
// ***********************
this._serialize(root.Left, sb)
this._serialize(root.Right, sb)
}const SEP = ",";
const NULL = "#";
var serialize = function(root) {
var sb = [];
_serialize(root, sb);
return sb.join('');
};
var _serialize = function(root, sb){
if(root === null) {
sb.push(NULL);
sb.push(SEP);
return;
}
// ****** Preorder position ********
sb.push(root.val);
sb.push(SEP);
// ***********************
_serialize(root.left, sb);
_serialize(root.right, sb);
};现在，思考一下如何写 deserialize 函数，将字符串反过来构造二叉树。
首先我们可以把字符串转化成列表：
String data = "1,2,#,4,#,#,3,#,#,";
String[] nodes = data.split(",");string data = "1,2,#,4,#,#,3,#,#,";
vector<string> nodes;
stringstream ss(data);
string item;
while(getline(ss, item, ',')) {
nodes.push_back(item);
}data = "1,2,#,4,#,#,3,#,#,"
nodes = data.split(",")data := "1,2,#,4,#,#,3,#,#,"
nodes := strings.Split(data, ",")var data = "1,2,#,4,#,#,3,#,#,";
var nodes = data.split(",");In this way, the nodes list is the preorder traversal result of the binary tree. The problem now is: how to reconstruct a binary tree from its preorder traversal result?
提示
In the previous article Binary Tree Construction with Dong Ge, we mentioned that at least two traversal orders (preorder, inorder, or postorder) are needed to reconstruct a binary tree. That's because the previous traversal results did not record the information of null pointers. Here, the nodes list contains information about null pointers, so we can reconstruct the binary tree using only the nodes list.
Based on our analysis, the nodes list represents a flattened binary tree:
Therefore, the deserialization process is similar: first determine the root node root, then follow the preorder traversal rules to recursively generate the left and right subtrees: