东哥带你刷二叉树（序列化篇） :: labuladong的算法小抄 #992

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import collections
from typing import List
NULL = 1001
class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        ans = []

        def traverse(node):
            if not node:
                ans.append(NULL)
                return
            ans.append(node.val)
            traverse(node.left)
            traverse(node.right)

        if not root:
            return ""
        traverse(root)
        return ",".join([str(ele) for ele in ans])

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == "":
            return None
        data = [int(ele) for ele in data.split(",")]

        def deserivalize_pre(data: List) -> TreeNode:
            if not data:
                return None
            val = data.popleft()
            if val == NULL:
                return None
            root = TreeNode(val)
            root.left = deserivalize_pre(data)
            root.right = deserivalize_pre(data)
            return root
        return deserivalize_pre(collections.deque(data))

# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

0 replies

lxw665 · 2022-05-13T06:03:55Z

lxw665
May 13, 2022

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
// Encodes a tree to a single string.
    String NULL = "#";
    String SEP = ",";
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serializeHelp(root, sb);
        return sb.toString();
    }

    public void serializeHelp(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SEP);
            return;
        }
        sb.append(root.val).append(SEP);
        serializeHelp(root.left, sb);
        serializeHelp(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.length() == 0) {
            return null;
        }
        String[] nodes = data.split(",");
        TreeNode root = deserializeHello(nodes);
        return root;
    }

    int nodesStart = 0;
    public TreeNode deserializeHello(String[] nodes) {
        if (nodesStart > nodes.length) {
            return null;
        }
        if (nodes[nodesStart].equals("#")) {
            nodesStart++;
            return null;
        }
        int rootVal = new Integer(nodes[nodesStart]);
        nodesStart++;
        TreeNode root = new TreeNode(rootVal);
        root.left = deserializeHello(nodes);
        root.right = deserializeHello(nodes);
        return root;
    }
}

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

2 replies

hemw Feb 18, 2023 — with giscus

就是让数组一直往前推进，递归构建出所有的子树，这道题不能以前一篇构造篇的思路去解，不然会陷入想去找两个子树的index去递归这样就出不来了

WheelChen Apr 13, 2023 — with giscus

我就是想找到来个子树的index 想了好久没整出来

gaoxiaoduan · 2022-05-30T03:08:46Z

gaoxiaoduan
May 30, 2022

js版本：
在反序列化时，使用指针优化时间复杂度

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  let res = [];
  const traverse = (root) => {
    if (root === null) return res.push("Null");
    res.push(root.val);
    traverse(root.left);
    traverse(root.right);
  };
  traverse(root);
  return res.toString();
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  const nodes = data.split(",");
  let p = 0;
  const deTraverse = (nodes) => {
    // if (nodes[0] === "Null") {
    //   nodes.shift();
    if (nodes[p] === "Null") {
      p++;
      return null;
    }
    // const root = new TreeNode(parseInt(nodes[0]));
    // nodes.shift();
    const root = new TreeNode(parseInt(nodes[p]));
    p++;

    root.left = deTraverse(nodes);
    root.right = deTraverse(nodes);
    return root;
  };

  return deTraverse(nodes);
};

0 replies

LeroyPine · 2022-05-30T11:16:09Z

LeroyPine
May 30, 2022

序列化&反序列化｜等同于加密&解密。按照算法加密，在按照算法解密。
本质是按照定义的结构去加去解

0 replies

mortal-94 · 2022-06-07T10:15:24Z

mortal-94
Jun 7, 2022

C++版（感觉就像再考字符串操作，查了一堆字符串string类的操作 😂

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec
{
public:
    string StringBuilder;
    // 通过前序遍历来进行序列化 间隔符位 ,  空指针为 #
    void preordercoding(TreeNode *root)
    {
        if (root == nullptr)
        {
            StringBuilder.append("#");
            StringBuilder.append(",");
            return;
        }
        StringBuilder.append(to_string(root->val));
        StringBuilder.append(",");
        preordercoding(root->left);
        preordercoding(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode *root)
    {
        StringBuilder.clear();
        preordercoding(root);
        return StringBuilder;
    }
    
    // 反序列化
    TreeNode *preorderdecoding(string &data)
    {
        // 字符串已经空了，返回空指针
        if (data.empty())
            return nullptr;
        // 发现是 , 删掉
        if (data[0] == ',')
            data.erase(data.begin());
        // 发现是 # 删掉 并 返回空指针
        if (data[0] == '#')
        {
            data.erase(data.begin());
            return nullptr;
        }
        // 数值获取 以及 删掉字符串中的数值
        size_t sz;
        TreeNode *root = new TreeNode(stoi(data, &sz));
        data.erase(0, sz);
        // 递归
        root->left = preorderdecoding(data);
        root->right = preorderdecoding(data);
        // 返回该层完成的树
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data)
    {
        return preorderdecoding(data);
    }
};

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

0 replies

xmh294450886 · 2022-06-08T08:06:40Z

xmh294450886
Jun 8, 2022

前序的反序列如何判断root.left的长度？

0 replies

lzwanan · 2022-06-16T02:45:38Z

lzwanan
Jun 16, 2022

解题思路

Java
后序遍历的序列化与反序列化

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    /**
     * 分隔符
     */
    final String SPLIT = ",";

    /**
     * 空节点
     */
    final String NULL = "NULL";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    private void serialize(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(NULL).append(SPLIT);
            return;
        }

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

        // 后序遍历位置
        sb.append(root.val).append(SPLIT);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for (String nodeVal : data.split(SPLIT)) {
            nodes.addLast(nodeVal);
        }
        return deserialize(nodes);
    }

    private TreeNode deserialize(LinkedList<String> nodes) {
        if (nodes.isEmpty()) {
            return null;
        }

        // 后序遍历的最后一个节点，即根节点
        String rootVal = nodes.removeLast();
        if (NULL.equals(rootVal)) {
            return null;
        }

        // 构造根节点
        TreeNode root = new TreeNode(Integer.parseInt(rootVal));
        // 先构造右子树，再构造左子树
        root.right = deserialize(nodes);
        root.left = deserialize(nodes);
        return root;
    }
}

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

0 replies

lzwanan · 2022-06-16T03:28:41Z

lzwanan
Jun 16, 2022

解题思路

Java 层序遍历序列化与反序列化

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    /**
     * 分隔符
     */
    final String SPLIT = ",";

    /**
     * 空节点
     */
    final String NULL = "NULL";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) {
            return "";
        }
        StringBuilder sb = new StringBuilder();

        // 新建队列
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);

        while (!nodes.isEmpty()) {
            // 弹出当前节点
            TreeNode currentNode = nodes.poll();

            // 层序遍历开始
            if (currentNode == null) {
                sb.append(NULL).append(SPLIT);
                continue;
            }
            sb.append(currentNode.val).append(SPLIT);
            // 层序遍历结束

            nodes.offer(currentNode.left);
            nodes.offer(currentNode.right);
        }

        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data.isEmpty()) {
            return null;
        }
        String[] nodeValues = data.split(SPLIT);
        // 数组的第一个值，就是根节点的值
        TreeNode root = new TreeNode(Integer.parseInt(nodeValues[0]));

        // 新建队列 存放根节点
        Queue<TreeNode> nodes = new LinkedList<>();
        nodes.offer(root);

        for (int i = 1; i < nodeValues.length; ) {
            // 弹出当前节点
            TreeNode parent = nodes.poll();
            // 获取左节点
            String left = nodeValues[i++];
            if (!NULL.equals(left)) {
                parent.left = new TreeNode(Integer.parseInt(left));
                nodes.offer(parent.left);
            } else {
                parent.left = null;
            }

            // 获取右节点
            String right = nodeValues[i++];
            if (!NULL.equals(right)) {
                parent.right = new TreeNode(Integer.parseInt(right));
                nodes.offer(parent.right);
            } else {
                parent.right = null;
            }
        }

        return root;
    }
}

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

0 replies

tanlandy · 2022-06-19T18:14:08Z

tanlandy
Jun 19, 2022

Python两种方法，附解释和代码

前序遍历

class Codec:

    def serialize(self, root):
        """
        用一个list记录，最后转为string导出：前序遍历，空节点计作N，然后用,连接
        """
        res = []
        def dfs(node):
            if not node:
                res.append("N")
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        
        dfs(root)
        return ",".join(res)

    def deserialize(self, data):
        """
        转化为list，然后用i遍历
        先确定根节点 root，然后遵循前序遍历的规则，递归生成左右子树
        """
        vals = data.split(",")
        self.i = 0
        
        def dfs():
            if vals[self.i] == "N":
                self.i += 1
                return None
            node = TreeNode(int(vals[self.i]))
            self.i += 1
            node.left = dfs()
            node.right = dfs()
            return node
        
        return dfs()

层序遍历

class Codec:

    def serialize(self, root):
        """
        用queue，把root添加进来，如果有值就加入res[]，并且更新左右子树，如果是空就跳过。
        """
        if not root:
            return ""
        res = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if not node:
                res.append("N")
                continue
            res.append(str(node.val))
            queue.append(node.left)
            queue.append(node.right)
        
        return ",".join(res)
        

    def deserialize(self, data):
        if not data:
            return None
        vals = data.split(",")
        root = TreeNode(int(vals[0]))
        queue = collections.deque()
        queue.append(root)
        i = 1
        while queue and i < len(vals):
            node = queue.popleft()
            if vals[i] != "N":
                left = TreeNode(int(vals[i]))
                node.left = left
                queue.append(left)
            i += 1
            if vals[i] != "N":
                right = TreeNode(int(vals[i]))
                node.right = right
                queue.append(right)
            i += 1
        
        return root

0 replies

treeforest · 2022-07-22T02:56:51Z

treeforest
Jul 22, 2022

Golang 层序遍历

前面一个忘记贴格式了

type Codec struct {
    
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    queue := []*TreeNode{root}
    s := []string{strconv.Itoa(root.Val)}
    for len(queue) != 0 {
        n := len(queue)
        for i := 0; i < n; i++ {
            node := queue[i]
            if node.Left != nil {
                s = append(s, strconv.Itoa(node.Left.Val))
                queue = append(queue, node.Left)
            } else {
                s = append(s, "")
            }
            if node.Right != nil {
                s = append(s, strconv.Itoa(node.Right.Val))
                queue = append(queue, node.Right)
            } else {
                s = append(s, "")
            }
        }
        queue = queue[n:]
    }
    return strings.Join(s, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    if data == "" {
        return nil
    }
    s := strings.Split(data, ",")
    i := 0
    root := &TreeNode{Val: this.Atoi(s[i])}
    i++
    queue := []*TreeNode{root}
    for len(queue) != 0 {
        n := len(queue)
        for j := 0; j < n; j++ {
            node := queue[j]
            if s[i] != "" {
                node.Left = &TreeNode{Val: this.Atoi(s[i])}
                queue = append(queue, node.Left)
            } else {
                node.Left = nil
            }
            i++
            if s[i] != "" {
                node.Right = &TreeNode{Val: this.Atoi(s[i])}
                queue = append(queue, node.Right)
            } else {
                node.Right = nil
            }
            i++
        }
        queue = queue[n:]
    }
    return root
}

func (this *Codec) Atoi(s string) int {
    v, _ := strconv.Atoi(s)
    return v
}

0 replies

yonggui-yan · 2022-09-05T15:05:20Z

yonggui-yan
Sep 5, 2022

打卡

0 replies

shallowshadowshade · 2022-09-08T08:07:57Z

shallowshadowshade
Sep 8, 2022 — with giscus

C++前序

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    string StringBuilder;
    //通过前序遍历来进行序列化，间隔符“，”，空指针为“#”
    void preordercoding(TreeNode* root)
    {
        if (root == nullptr)
        {
            StringBuilder.append("#");//空指针就加入#号
            StringBuilder.append(",");//每一个字符后都得加入逗号，
            return;
        }
        StringBuilder.append(to_string(root->val));//非空加入数值
        StringBuilder.append(",");
        preordercoding(root->left);
        preordercoding(root->right);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        StringBuilder.clear();//先清空，准备进行构造
        preordercoding(root);
        return StringBuilder;
    }

    //反序列化
    TreeNode* preorderdecoding(string &data)
    {
        if (data.empty()) return nullptr;
        //如果字符为“，”，则删除
        if (data[0] == ',') data.erase(data.begin());
        //如果是#说明第一个元素都是这个，返回空指针
        if (data[0] == '#') 
        {
            data.erase(data.begin());
            return nullptr;
        }
        //数值获取
        auto sz = sizeof(data);//实际上是size_t类型，就是获取字符串的长度
        TreeNode* root = new TreeNode(stoi(data, &sz));
        //参数2的&不能丢，因为源代码当中是size_t *idx这个指针，所以需要取地址符
        //stoi()函数都是只转换字符串的数字部分，如果遇到其它字符的话则停止转换。
        data.erase(0, sz);
        //递归
        root->left = preorderdecoding(data);//因为加入的时候也是先left后right的
        root->right = preorderdecoding(data);

        //返回该层完成的树
        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        return preorderdecoding(data);
    }
};

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

0 replies

jxs1211 · 2022-10-09T02:00:47Z

jxs1211
Oct 9, 2022 — with giscus

Here is the AC solution of Go's version

type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {return ""}
    s := []string{}
    dfs(root, &s)
    fmt.Println(s)
    return strings.Join(s, ",")
}

func dfs(root *TreeNode, s *[]string) {
    if root == nil {
        *s = append(*s, "null")
        return
    }
    *s = append(*s, strconv.Itoa(root.Val))
    dfs(root.Left, s)
    dfs(root.Right, s)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if len(data) == 0 {return nil}
    s := strings.Split(data, ",")
    return build(&s)
}
// 
func build(datas *[]string) *TreeNode {
    if len(*datas) == 0{return nil}
    rootVal := (*datas)[0]
    *datas = (*datas)[1:]
    if rootVal == "null" {
        return nil
    }
    val, _ := strconv.Atoi(rootVal)
    return &TreeNode{
        Val: val,
        Left: build(datas),
        Right: build(datas),
    }
}

0 replies

jxs1211 · 2022-10-09T04:26:44Z

jxs1211
Oct 9, 2022 — with giscus

use preorder string to representative the tree node:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// preorder -> serialize
type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
    
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    s := strings.Split(data, ",")
    return build(&s)
}
// 
func build(datas *[]string) *TreeNode {
    if len(*datas) == 0{return nil}
    rootVal := (*datas)[0]
    *datas = (*datas)[1:]
    if rootVal == "#" {
        return nil
    }
    val, _ := strconv.Atoi(rootVal)
    return &TreeNode{
        Val: val,
        Left: build(datas),
        Right: build(datas),
    }
}
/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

use postorder string to representative the tree node:

// preorder -> serialize
type Codec struct {
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return "#"
    }
    // return this.serialize(root.Left) + "," + strconv.Itoa(root.Val) + "," + this.serialize(root.Right)
    return this.serialize(root.Left) + "," + this.serialize(root.Right) + "," + strconv.Itoa(root.Val)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    s := strings.Split(data, ",")
    return build2(&s)
}

func build2(datas *[]string) *TreeNode {
    if len(*datas) == 0 {return nil}
    ele := (*datas)[len(*datas) - 1]
    *datas = (*datas)[:len(*datas) - 1]
    if ele == "#" {return nil}
    val, _ := strconv.Atoi(ele)
    return &TreeNode{
        Val: val,
        Right: build2(datas),
        Left: build2(datas),
    }
}

0 replies

Youareblind · 2022-10-21T18:39:34Z

Youareblind
Oct 21, 2022

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/** Encodes a tree to a single string. */
#define SIZE 50000
void traverse(struct TreeNode *tree, char *data, int *index)
{
    data[(*index)++] = ',';

    if(tree == NULL)
    {
        data[(*index)++] = '#';
        return;
    }

    int elem = tree->val;
    int stack[4], top = 0;
    if(elem == 0)
        data[(*index)++] = '0';
    if(elem < 0)
    {
        data[(*index)++] = '-';
        elem = -elem;
    }
    while(elem > 0)
    {
        stack[top++] = elem % 10;
        elem /= 10;
    }
    while(top > 0)
        data[(*index)++] = stack[--top] + '0';

    traverse(tree->left, data, index);
    traverse(tree->right, data, index);
  
}

char* serialize(struct TreeNode* root) 
{
    char *data = (char *)malloc(SIZE * sizeof(char));
    int index = 0;
    traverse(root, data, &index);  
    data[index] = '\0';

    return data;      
}

/** Decodes your encoded data to tree. */
struct TreeNode* des(char* data, int *index) 
{
    (*index)++;

    struct TreeNode *tree;

    if(data[(*index)] == '#' || data[(*index)] == '\0')
    {
        tree = NULL;
        (*index)++;
    }
    else
    {
        int neg_flag = 0, elem = 0;

        if(data[(*index)] == '0')
            (*index)++;
        else
        {
            if(data[(*index)] == '-')
            {
                neg_flag = 1;
                (*index)++;
            }
            while(data[(*index)] != ',')
            {
                elem = 10 * elem + (data[(*index)] - '0');
                (*index)++;
            }
            if(neg_flag)
                elem = -elem;
        }
        tree = (struct TreeNode *)malloc(sizeof(struct TreeNode));
        tree->val = elem;
        tree->left = des(data, index);
        tree->right = des(data, index);
    }
    return tree;
}

struct TreeNode* deserialize(char* data)
{
    int index = 0;
    return des(data, &index);
}

// Your functions will be called as such:
// char* data = serialize(root);
// deserialize(data);

0 replies

littlesquirrel2017 · 2022-11-22T13:43:20Z

littlesquirrel2017
Nov 22, 2022 — with giscus

c++解法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    string ser;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (root == nullptr) return ser;
        preorder(root);
        return ser;
    }
    void preorder(TreeNode* root) {
        if (root == nullptr) {
            ser.append("#");
            ser.append(",");
            return;
        }
        ser.append(std::to_string(root->val));
        ser.append(",");
        preorder(root->left);
        preorder(root->right);
    }

    // Decodes your encoded data to tree.
    TreeNode* rdeserialize(vector<string>& dataArray) {
        if (dataArray.front() == "#") {
            dataArray.erase(dataArray.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdeserialize(dataArray);
        root->right = rdeserialize(dataArray);
        return root;
    }

    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        vector<string> dataArray;
        string str;
        for (auto& ch : data) {  
            if (ch == ',') {
                dataArray.push_back(str);
                str.clear();
            } else {
                str.push_back(ch);
            }
        }
        if (!str.empty()) {
            dataArray.push_back(str);
            str.clear();
        }
        
        return rdeserialize(dataArray);
    }

};

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

0 replies

NayelyA · 2022-12-03T15:41:41Z

NayelyA
Dec 3, 2022 — with giscus

前序遍历 golang

type Codec struct {
    Nodes []string
}

func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    this.serializable(root)
    return strings.Join(this.Nodes, ",")
}

func (this *Codec) serializable(root *TreeNode) {
    if root == nil {
        this.Nodes = append(this.Nodes,"#")
        return 
    }
    this.Nodes = append(this.Nodes,strconv.Itoa(root.Val))
    this.serializable(root.Left)
    this.serializable(root.Right)
}


// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    this.Nodes =[]string{}
    for _, v := range strings.Split(data, ",") {
		this.Nodes = append(this.Nodes, v)
	}
    return this.deserializable()
}


func (this *Codec)deserializable() *TreeNode{
    if len(this.Nodes) == 0 {
        return nil
    }
    rootVal:=this.Nodes[0]
    this.Nodes = this.Nodes[1:]
    if rootVal == "#" {
        return nil
    }
    root:= new (TreeNode)
    root.Val , _ = strconv.Atoi(rootVal)
    root.Left = this.deserializable()
    root.Right = this.deserializable()
    return root
}

0 replies

weixueman · 2023-01-12T12:07:11Z

weixueman
Jan 12, 2023 — with giscus

反序列化可以使用数组作为参数，这点确实没想到。感觉被前面的构造篇局限了思维，只想到要用数组配合左右指针

0 replies

bruceeewong · 2023-01-16T22:48:58Z

bruceeewong
Jan 16, 2023 — with giscus

20230116 打卡～层序遍历的正反序列化都用队列进行层序遍历；反序列化通过移动字符串数组下标来取到左右节点的值，从而正确按层序恢复树，思路好棒

0 replies

xiaohanhanfei · 2023-03-31T08:34:50Z

xiaohanhanfei
Mar 31, 2023 — with giscus

C++实现

class Codec { 
     public:
          string SEP = ",";
          string null = "#";
        string serialize(TreeNode* root) {
        string str = "";
        traverse(root, str); 
        return str;  
    }
    void traverse(TreeNode* root, string& str){
         
         if(root == NULL) {
             str += null + SEP;
             return;
         } 
         
         str += to_string(root->val) + SEP;
         traverse(root->left ,str);
         traverse(root->right, str);
    }

    // Decodes your encoded data to tree.

    TreeNode* deserialize(string data) {
        istringstream iss(data);  //分割成子字符
        return destraverse(iss);
    }

    TreeNode* destraverse(istringstream& iss) {
        string val;
        getline(iss, val, ',');  //把每个子字符存入val ，，以，号分割来存
        if (val == null) return nullptr;
      
        TreeNode* root = new TreeNode(stoi(val));
        root->left = destraverse(iss);
        root->right = destraverse(iss);
        return root;
    }
};

0 replies

mangohow · 2023-04-27T09:21:40Z

mangohow
Apr 27, 2023 — with giscus

golang前序遍历，使用二进制编码

type Codec struct {
	null int16
}

func Constructor() Codec {
	return Codec{
		null: math.MaxInt16,
	}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil {
		return ""
	}
	buff := bytes.NewBuffer(nil)
	this.serializeNode(root, buff)
	return buff.String()
}

func (this *Codec) serializeNode(root *TreeNode, buff *bytes.Buffer) {
	if root == nil {
		binary.Write(buff, binary.LittleEndian, this.null)
		return
	} else {
		binary.Write(buff, binary.LittleEndian, int16(root.Val))
	}

	this.serializeNode(root.Left, buff)
	this.serializeNode(root.Right, buff)
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	reader := bytes.NewReader([]byte(data))
	return this.buildTree(reader)
}

func (this *Codec) buildTree(reader io.Reader) *TreeNode {
	val := int16(0)
	binary.Read(reader, binary.LittleEndian, &val)
	if val == this.null {
		return nil
	}

	root := &TreeNode{Val: int(val)}
	root.Left = this.buildTree(reader)
	root.Right = this.buildTree(reader)

	return root
}
```go

0 replies

iiimapidan · 2023-06-04T15:46:06Z

iiimapidan
Jun 4, 2023 — with giscus

如果你的序列化结果中不包含空指针的信息，且你会给出两种遍历顺序，那么按照前文东哥手把手带你刷二叉树（构造篇）所说，分两种情况：
2.2. 如果你给出前序和后序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。

如果你的序列化结果中包含空指针的信息，且你只给出一种遍历顺序，也要分两种情况：
3.2. 如果你给出的是中序，那么除非你的整棵树中不包含值相同的节点，否则你无法还原出唯一的一棵二叉树。

为啥整棵树中不包含值相同的节点就可以还原一棵二叉树？这个也不一定吧

2 replies

crowyyyy Jun 10, 2023 — with giscus

+1疑惑，感觉即使不包含相同节点也不一定能还原唯一一颗二叉树

labuladong Jun 13, 2023
Maintainer Author

谢谢指正，是我写错了，已修改~

treeforest · 2023-06-04T15:46:27Z

treeforest
Jun 4, 2023

收到了，谢谢~~

0 replies

outsmartchad · 2023-07-20T06:01:32Z

outsmartchad
Jul 20, 2023 — with giscus

C++ - BFS - level order traversal 層級遍歷解法

    // main function for deserialize
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return nullptr;
        vector<string> nodes;
        string cur = "";
        for (char& c : data) {
            if (c == ',') {
                nodes.push_back(cur);
                cur.clear();
            } else {
                cur.push_back(c);
            }
        }
        if (!cur.empty()) {
            nodes.push_back(cur);
        }
        if(nodes.front()=="#") return nullptr;
        TreeNode* root = new TreeNode(stoi(nodes.front()));
        queue<TreeNode*> q;
        q.push(root);
        int index = 1;
        while (!q.empty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                TreeNode* parent = q.front();q.pop();
                string left = nodes[index++];
                if(left=="#"){
                    parent->left = NULL;
                }else{
                    parent->left = new TreeNode(stoi(left));
                    q.push(parent->left);
                }
                string right = nodes[index++];
                if(right=="#"){
                    parent->right = NULL;
                }
                else{
                    parent->right = new TreeNode(stoi(right));
                    q.push(parent->right);
                }
            }
        }
        return root;
    }  
    // main function for serialize
    // Encodes a tree to a single string.
    string serialize(TreeNode* root){
        string data = "";
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int sz = q.size();
            for(int i =0; i<sz; i++){
                TreeNode* cur = q.front();
                q.pop();
                if(!cur) {
                    data.append("#").append(",");
                    continue;
                }
                data.append(to_string(cur->val)).append(",");
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        return data;
    }

0 replies

treeforest · 2023-07-20T06:01:56Z

treeforest
Jul 20, 2023

收到了，谢谢~~

0 replies

东哥带你刷二叉树（序列化篇） :: labuladong的算法小抄 #992

labuladong Feb 5, 2022 Maintainer

Replies: 32 comments · 5 replies

hemw Feb 18, 2023 — with giscus

WheelChen Apr 13, 2023 — with giscus

解题思路

代码

解题思路

代码

Python两种方法，附解释和代码

前序遍历

层序遍历

Golang 层序遍历

shallowshadowshade Sep 8, 2022 — with giscus

jxs1211 Oct 9, 2022 — with giscus

jxs1211 Oct 9, 2022 — with giscus

use preorder string to representative the tree node:

use postorder string to representative the tree node:

littlesquirrel2017 Nov 22, 2022 — with giscus

NayelyA Dec 3, 2022 — with giscus

weixueman Jan 12, 2023 — with giscus

bruceeewong Jan 16, 2023 — with giscus

xiaohanhanfei Mar 31, 2023 — with giscus

mangohow Apr 27, 2023 — with giscus

golang前序遍历，使用二进制编码

iiimapidan Jun 4, 2023 — with giscus

crowyyyy Jun 10, 2023 — with giscus

labuladong Jun 13, 2023 Maintainer Author

outsmartchad Jul 20, 2023 — with giscus

labuladong
Feb 5, 2022
Maintainer

Replies: 32 comments 5 replies

shallowshadowshade
Sep 8, 2022 — with giscus

jxs1211
Oct 9, 2022 — with giscus

jxs1211
Oct 9, 2022 — with giscus

littlesquirrel2017
Nov 22, 2022 — with giscus

NayelyA
Dec 3, 2022 — with giscus

weixueman
Jan 12, 2023 — with giscus

bruceeewong
Jan 16, 2023 — with giscus

xiaohanhanfei
Mar 31, 2023 — with giscus

mangohow
Apr 27, 2023 — with giscus

iiimapidan
Jun 4, 2023 — with giscus

labuladong Jun 13, 2023
Maintainer Author

outsmartchad
Jul 20, 2023 — with giscus