algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-d14d3/

[giscus[bot]]

algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-d14d3/

Info 数据结构精品课 (https://aep.h5.xeknow.com/s/1XJHEO) 和 递归算法专题课 (https://aep.xet.tech/s/3YGcq3) 限时附赠网站会员！ 读完本文，你不仅学会了算法套路，还可以顺便解决如下题目： LeetCode 力扣 难度 :----: :----: :----: 297. Seria...

https://labuladong.gitee.io/algo/di-yi-zhan-da78c/shou-ba-sh-66994/dong-ge-da-d14d3/

[Jiminyang1]

“...比如我们经常将“变成”语言中的结构体序列化成 JSON 字符串” 编程 可能打太快了

[henrylolol]

不过我们在反序列化的过程中是需要记录空指针 null 的，所以可以把标准的层级遍历框架略作修改：

void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue q = new LinkedList<>();
q.offer(root);

while (!q.isEmpty()) {
    int sz = q.size();
    for (int i = 0; i < sz; i++) {
        TreeNode cur = q.poll();
        /* 层级遍历代码位置 */
        if (cur == null) continue;
        System.out.println(root.val);
        /*****************/
        q.offer(cur.left);
        q.offer(cur.right);
    }
    
}

}

第13行应该是System.out.println(cur.val);

[ForeverCm]

但它俩的中序遍历结果都是 [#,1,#,1,#]

这句有个疑惑，我认为左边树中序是 [#,#,1,1,#]，右边树中序是[#,1,1,#,#]

[ljw19970]

对于层序遍历的C++解法，deserialize中取出第一个元素(root)后也应该对其进行是否为"NULL"的判断吧

[myalice-forever]

前序遍历的c++反序列化代码写错了，应该先构造root->left再构造root->right，因为为了减少时间复杂度reverse了数组之后，左子树依然是紧挨着根节点的右半侧数组。

[Valor-H]

class Codec {
private:
// 将序列化数据放在数组中, 方便操作
vector strs;
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
// 碰到空节点的情况
if (root == nullptr) return "#";
string left = serialize(root->left);
string right = serialize(root->right);
string cur = left + "," + right + "," + to_string(root->val);
return cur;
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    int pos = 0;
    while ((pos = data.find(",")) != data.npos) {
        strs.push_back(data.substr(0, pos));
        data.erase(0, pos + 1);
    }
    strs.push_back(data);
    return build();
}

// 构造二叉树
TreeNode* build() {
    if (strs.empty()) return nullptr;
    // 找到根节点
    string s = strs.back();
    strs.pop_back();
    if (s == "#") return nullptr;
    TreeNode* node = new TreeNode(stoi(s));
    node->right = build();
    node->left = build();
    return node;
}

};

[CZT0]

golang 先序

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

// 序列化二叉树为字符串。
func (this *Codec) serialize(root *TreeNode) string {
    // 如果节点为空，则返回"null,"。
    if root == nil {
        return "null,"
    }
    // 使用先序遍历，首先添加当前节点的值，然后递归处理左右子树。
    return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + this.serialize(root.Right)
}

// 将序列化的字符串反序列化为二叉树。
func (this *Codec) deserialize(data string) *TreeNode {
    // 以逗号为分隔符，将字符串分割成切片。
    array := strings.Split(data, ",")
    // 使用辅助函数buildTree来构建并返回树。
    return this.buildTree(&array)
}

// 辅助函数，用于从字符串数组构建二叉树。
func (this *Codec) buildTree(data *[]string) *TreeNode {
    // 检查数组的第一个元素。如果是"null"，表示当前位置应该是空节点。
    if (*data)[0] == "null" {
        // 移除已处理的第一个元素。
        *data = (*data)[1:]
        return nil
    }

    // 将字符串转换为整数，作为节点的值。
    val, _ := strconv.Atoi((*data)[0])
    // 移除已处理的第一个元素。
    *data = (*data)[1:]
    // 创建新节点。
    node := &TreeNode{Val: val}
    // 递归构建左子树。
    node.Left = this.buildTree(data)
    // 递归构建右子树。
    node.Right = this.buildTree(data)
    return node
}



/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */