九号球普通 2023年11月19日上午11:41

“`java
难点是二叉树的唯一性和反序列化时的左右确定
public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
    StringBuilder builder = new StringBuilder();
    rSerialize(root, builder);
    return builder.substring(0, builder.length() - 1);
}

public void rSerialize(TreeNode root, StringBuilder builder) {
    if (root == null) {
        builder.append("none").append(",");
        return;
    }
    builder.append(root.val).append(",");
    rSerialize(root.left, builder);
    rSerialize(root.right, builder);
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String[] arr = data.split(",");
    return rdeserialize(new LinkedList<String>(Arrays.asList(arr)));
}

public TreeNode rdeserialize(List<String> list) {
    if (list.get(0).equals("none")) {
        list.remove(0);
        return null;
    }
    TreeNode root = new TreeNode(Integer.valueOf(list.remove(0)));
    root.left = rdeserialize(list);
    root.right = rdeserialize(list);
    return root;
}

}

0 赞同 0 条回复

招舟子普通 2023年8月26日下午7:56

/**
* 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.
public String serialize(TreeNode root) {
    if(root==null){
        return null;
    }
    StringBuilder build = new StringBuilder();
    Queue<TreeNode> q = new LinkedList();

    q.offer(root);
    while(!q.isEmpty()){
        TreeNode node = q.poll();
        if(node!=null){
            build.append(node.val+",");
            q.offer(node.left);
            q.offer(node.right);
        }else{
            build.append("null,");
        }
    }
    return build.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data==null||data.length()==0){
        return null;
    }
    String[] s = data.split(",");
    Queue<TreeNode> q = new LinkedList();
    TreeNode node = new TreeNode(Integer.parseInt(s[0]));
    q.offer(node);
    int i = 1;
    while(!q.isEmpty()){
        TreeNode t = q.poll();
        if(!s[i].equals("null")){
            t.left = new TreeNode(Integer.parseInt(s[i]));
            q.offer(t.left);
        }
        i++;
        if(!s[i].equals("null")){
            t.right = new TreeNode(Integer.parseInt(s[i]));
            q.offer(t.right);
        }
        i++;
    }
    return node;
}

}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
字符串数组与队列之间的关系

0 赞同 0 条回复

jhfuture 普通 2023年8月15日下午9:45

“`java
两个函数时间、空间复杂度都是为 O（n）

public class Codec {

// 序列化，使用层次遍历构建出一个字符串。
// 层次遍历，使用队列，并同时保存null
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(rootnull) return “”;
StringBuilder s= new StringBuilder();
Queue q=new LinkedList();
q.add(root);
while(!q.isEmpty()){
TreeNode t= q.poll();
// 不为空则加入左右结点
if(t!=null){
s.append(t.val+”,”);
q.add(t.left);
q.add(t.right);
}else{
// 为空则加入null
s.append(“null,”);
}
}
return s.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if(data=="null"||data=="") return null;
        // 将data转化为 数组，然后建立一个队列进行处理
        int i=1;
        String[] array= data.split(",");
    Queue<TreeNode> q=new LinkedList<TreeNode>();
    TreeNode root= new TreeNode(Integer.parseInt(array[0]));
    q.add(root);
    while(!q.isEmpty()){
        TreeNode t= q.poll();
        if(!array[i].equals("null")){
            //有左节点
            TreeNode left=new TreeNode(Integer.parseInt(array[i]));
            t.left=left;
            q.add(left);
        }
        i++;
        if(!array[i].equals("null")){
          //有右节点
            TreeNode right=new TreeNode(Integer.parseInt(array[i]));
            t.right=right;
            q.add(right);
        }
        i++;
    }
return root;
}

}

0 赞同 0 条回复

CV大神普通 2023年7月20日下午2:56

public class Codec {

     // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null){
            return "[]";
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //这里不用链表，因为toString以后可能存在空格
        StringBuilder result = new StringBuilder();
        result.append("[");
        queue.addLast(root);
        while (!queue.isEmpty()){
            TreeNode node =  queue.pollFirst();
            if(node == null){
                result.append("null,");
            }else{
                result.append(node.val).append(",");
                queue.addLast(node.left);
                queue.addLast(node.right);
            }
        }
        result.deleteCharAt(result.length()-1);
        result.append("]");
        return result.toString();


    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 2){
            return null;
        }
        //去掉括号，同时字符串分割成字符串数组
        String[] array = data.substring(1,data.length()-1).split(",");
        //通过前序遍历的方式，挨个赋值和构造左右子树
        int i = 0;
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        TreeNode root = new TreeNode(Integer.parseInt(array[0]));
        queue.addLast(root);
        i++;
        while (!queue.isEmpty()){
            TreeNode node =  queue.pollFirst();
            if(!array[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(array[i]));
                queue.addLast(node.left);
            }
            i++;
            if(!array[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(array[i]));
                queue.addLast(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

断舍离永久会员 2023年7月13日下午4:17

public class Codec {

    /*
    * 序列化为字符串
    * */
    public String serialize(TreeNode root) {
        if(root == null){
            return "";
        }
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder str = new StringBuilder();
        queue.add(root);
        //层序遍历
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                str.append(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }else {
                str.append("null");
            }
            str.append(",");
        }
        //删除最后一个逗号
        str.deleteCharAt(str.length()-1);
        return str.toString();
    }

    /*
    * 反序列化为二叉树
    * */
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0){
            return null;
        }
        String[] s = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        //此处不能像序列化那样使用栈，先将右节点进栈
        //因为要保证先构建左节点，再构建右节点，来确保i的顺序增加，所以使用队列
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        //i用于记录节点位置
        //0索引的左节点是1，右节点是2;
        //1索引的左节点是3，右节点是4; 
        //2索引的左节点是5，右节点是6;  ... 以此类推
        int i = 1;
        while (!queue.isEmpty()){
            TreeNode node = queue.poll();
            //构建左节点
            if(!s[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                node.left = left;
                queue.add(left);
            }
            i++;
            //构建右节点
            if(!s[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                node.right = right;
                queue.add(right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月11日下午5:05

【思路】序列化时BFS遍历节点，将其转化为字符串拼接起来；反序列化逆向操作，两者都需要利用队列进行遍历。
【复杂度】时间空间均为O(n)

#include 
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        std::queue q;
        std::string s;
        q.push(root);

        while(!q.empty()) {
            TreeNode *node = q.front(); q.pop();
            if (node) {
                q.push(node->left);
                q.push(node->right);
                s += std::to_string(node->val) + ',';
            } else {
                s += "N,";
            }
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int pos = 0;
        auto parseOneNode = [&]() -> TreeNode* {
            if (data.at(pos) == 'N') {          // null node
                pos += 2;  
                return NULL;
            } else {                            // value node
                size_t end = data.find_first_of(',', pos);
                int val = std::stoi(data.substr(pos, end - pos), NULL);
                TreeNode *node = new TreeNode(val);
                pos = end + 1;
                return node;
            }
        };

        std::queue q;
        TreeNode *root = NULL;
        while (pos < data.size()) {
            if (q.empty()) {
                root = parseOneNode();
                q.push(root);
            } else {
                TreeNode *p = q.front(); q.pop();
                p->left = parseOneNode();
                p->right = parseOneNode();
                if(p->left) q.push(p->left);
                if(p->right) q.push(p->right);
            }
        }
        return root;
    }
};

0 赞同 0 条回复

憨憨永久会员 2023年7月11日下午12:56

看到层序遍历加入字符串就有点思路了，跟层序遍历一样稍微做一些改动，就是把null也进行入队操作，然后抛出null的时候就将null也加入字符串，中间加一个间隔符进行区分，反序列化的话就是按照层序遍历的思想来做，遇到null就赋null不入队，遍历完就可以了

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return "";
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        StringBuffer sb=new StringBuffer();
        while(!queue.isEmpty()){
            int a=queue.size();
            TreeNode temp=null;
            for(int i=0;i<a;i++){
                temp= queue.poll();
                if(temp==null){
                    sb.append("null,");
                }else{
                    sb.append(temp.val+",");
                    queue.offer(temp.left);
                    queue.offer(temp.right);
                }
            }
        }
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data==null||data.length()<=0)return null;
        String[] arr=data.split(",");
        Queue<TreeNode> queue=new LinkedList<>();
        TreeNode root=new TreeNode(Integer.valueOf(arr[0]));
        queue.offer(root);
        int id=0;
        while(!queue.isEmpty()){
            int a=queue.size();
            TreeNode temp=null;
            for(int i=0;i<a;i++){
                temp=queue.poll();
                String left=arr[++id];
                String right=arr[++id];
                if(left.equals("null")){
                    temp.left=null;
                }else{
                    temp.left=new TreeNode(Integer.valueOf(left));
                    queue.offer(temp.left);
                }
                if(right.equals("null")){
                    temp.right=null;
                }else{
                    temp.right=new TreeNode(Integer.valueOf(right));
                    queue.offer(temp.right);
                }
            }
        }
        return root;
    }
}

0 赞同 0 条回复

彦，，# 普通 2023年7月10日下午11:19

有点难
string serialize(TreeNode* root) {
        string res;
        if(!root) return res;
        queue<TreeNode*> q;
        q.push(root);

        while(!q.empty())
        {
            TreeNode* front = q.front();
            q.pop();
            if(front)
            {
                res += to_string(front->val) + ",";
                q.push(front->left);
                q.push(front->right);

            }
            else res+= "null,";
        }
        return res.substr(0, res.size() -1);

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty()) return nullptr;
        vector<string> s = split(data);

        queue<TreeNode*> q;
        TreeNode *root = new TreeNode(stoi(s[0]));
        q.push(root);
        int i = 1;
        while(!q.empty())
        {
            TreeNode* front = q.front();
            q.pop();
            if (s[i] != "null") {
                front->left = new TreeNode(stoi(s[i]));
                q.push(front->left);
            }
            ++i;
            if (s[i] != "null") {
                front->right = new TreeNode(stoi(s[i]));
                q.push(front->right);
            }
            ++i;
        }
        return root;

    }
    vector<string> split(string& s) {
        vector<string> res;
        int n = s.size();
        int i = 0;

        while (i < n) {
            int j = i + 1;
            while (j < n && s[j] != ',') ++j;
            res.push_back(s.substr(i, j - i));
            i = j + 1;
        }
        return res;
    }

0 赞同 0 条回复

Sexypig. 普通 2023年7月9日下午3:45

这段代码是一个用于序列化和反序列化二叉树的类。它使用层序遍历的方式将二叉树转化为一个字符串，并且可以将该字符串转化回原来的二叉树。
serialize方法接收一个二叉树的根节点作为参数，将二叉树序列化为一个字符串并返回。它使用了一个队列来进行层序遍历。首先将根节点加入队列，然后循环遍历队列中的节点，将节点的值转化为字符串并加入结果字符串中，同时将节点的左右子节点加入队列。如果节点为空，则将”null”加入结果字符串。最后返回结果字符串。
deserialize方法接收一个字符串作为参数，将该字符串反序列化为一个二叉树并返回。首先判断字符串是否为空，如果为空则返回nullptr。然后使用stringstream将字符串按照逗号分割成一个字符串数组。接着根据数组的第一个元素创建根节点。然后使用队列进行层序遍历，依次取出队列中的节点，根据字符串数组中的元素创建节点的左右子节点，并将其加入队列。最后返回根节点。
这段代码使用了队列和字符串流来实现二叉树的序列化和反序列化，是一种常用的实现方式。

#include <iostream>

using namespace std;

#include <queue>
#include <sstream>
#include <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:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        queue<TreeNode*> q;  // 层序遍历
        q.push(root);
        string res = "";  // 此处也可使用sstring装入流中，最后ss.str()即可
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (node) {
                res += to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            } else {
                res += "null,";
            }
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty() || data.size() == 0) return nullptr;
        queue<TreeNode*> q;
        vector<string> data_vec;
        stringstream ss(data);
        string item;
        while (
            getline(ss, item, ',')) {  // 此处用ss流+getline实现split(,)的功能
            data_vec.push_back(item);
        }
        TreeNode* root =
            new TreeNode(stoi(data_vec[0]));  // stoi将字符串转化为整型
        q.push(root);
        int i = 1;
        // 层序遍历
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();
            if (data_vec[i] != "null") {
                node->left = new TreeNode(stoi(data_vec[i]));
                q.push(node->left);
            }
            ++i;
            if (data_vec[i] != "null") {
                node->right = new TreeNode(stoi(data_vec[i]));
                q.push(node->right);
            }
            ++i;
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));

0 赞同 0 条回复

mpweixin用户普通 2023年7月7日上午10:35

java
public class Codec {
    //先根据层序遍历建立字符串，然后再根据层序遍历的特性重建二叉树
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "";
        }

        StringBuilder build = new StringBuilder(); //保存最终的字符串
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        while(!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(tmp != null) { //如果为不为空节点，就将左右子节点加入
                queue.add(tmp.left);
                queue.add(tmp.right);
                build.append(tmp.val + ",");
            } else {  //如果弹出的节点为空，那么就不需要压入左右子节点
                build.append(null + ",");
            }
        }
        return build.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0) {
            return null;
        }

        String[] string = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();   //将有值节点压入队列
        TreeNode root = new TreeNode(Integer.parseInt(string[0])); //建立根节点
        queue.add(root);
        int i = 1; //i is crusor, i的移动指向左右子节点

        while(!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            if(!string[i].equals("null")) {  //左节点
                TreeNode left = new TreeNode(Integer.parseInt(string[i]));
                tmp.left = left;
                queue.add(left);
            }
            i++;

            if(!string[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(string[i]));
                tmp.right = right;
                queue.add(right);
            }
            i++;
        }

        return root;
    }
}

按di哥思路来，时间和空间复杂度都是O(N)

0 赞同 0 条回复

局外人普通 2023年7月5日上午11:54

思路：因为有“#”表示空节点，按照前序遍历建立字符串，以及建立二叉树
时间复杂度： O(n) 空间复杂度：O(n)

public class Codec {

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

    public void serial(TreeNode root, StringBuilder sb){
        if(root==null){
            sb.append("#").append(",");
            return;
        }  
        sb.append(root.val).append(",");
        serial(root.left, sb);
        serial(root.right, sb);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> nodes = new LinkedList<>();
        for(String s:data.split(",")){
            nodes.add(s);
        }
        return deserial(nodes);
    }

    public TreeNode deserial(LinkedList<String> nodes){
        if(nodes.isEmpty()) return null;

        String first = nodes.removeFirst();
        if(first.equals("#"))   return null;
        TreeNode root=new TreeNode(Integer.parseInt(first));
        root.left = deserial(nodes);
        root.right = deserial(nodes);
        return root;
    }
}

0 赞同 0 条回复

屠龙手段普通 2023年7月4日下午5:31

层次遍历，时间复杂度O(n)，空间复杂度O(n)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return []
        str_lst = []
        return self.bfs(root, str_lst)

    def bfs(self, root, str_lst):
        queue = [root]
        while queue:
            cur, queue = queue[0], queue[1:]
            str_lst.append(str(cur.val)) if cur else str_lst.append('null')
            if cur:
                queue.append(cur.left) if cur.left else queue.append(None)
                queue.append(cur.right) if cur.right else queue.append(None)
        return str_lst

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        root, data = TreeNode(data[0]), data[1:]
        TreeNode_queue = [root]
        flag = True
        while data:
            cur, data = data[0], data[1:]
            tmp = TreeNode(int(cur)) if cur != 'null' else None
            if TreeNode_queue:
                pre = TreeNode_queue[0]
                if flag:
                    pre.left = tmp
                else:
                    pre.right = tmp
                    TreeNode_queue = TreeNode_queue[1:]
                flag = not flag
            if tmp:        
                TreeNode_queue.append(tmp)
        return root


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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月4日下午3:26

层序

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)
            return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node!=null){
                res.append(node.val+",");
                queue.offer(node.left);
                queue.offer(node.right);
            }
            else
                res.append("null,");
        }
        res.deleteCharAt(res.length()-1);
        res.append("]");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]"))
            return null;
        String[] vals = data.substring(1,data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(vals[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int i=1;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!vals[i].equals("null")){
                node.left = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.left);
            }
            i++;
            if(!vals[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(vals[i]));
                queue.offer(node.right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

花老爷普通 2023年7月3日下午3:07

dfs
时间：O(n)
空间：O(n)

public class Codec {
    private int idx = 0;

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

    private void rserialize(TreeNode root, StringBuffer sb) {
        if (root == null) {
            sb.append("null ");
        } else {
            sb.append(root.val);
            sb.append(" ");
            rserialize(root.left, sb);
            rserialize(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(" ");
        return rdeserialize(dataArray);
    }

    private TreeNode rdeserialize(String[] dataArray) {
        if (dataArray[idx].equals("null")) {
            return null;
        }
        TreeNode root = new TreeNode(Integer.valueOf(dataArray[idx]));
        idx++;
        root.left = rdeserialize(dataArray);
        idx++;
        root.right = rdeserialize(dataArray);
        return root;
    }
}

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月2日下午6:25

已经忘了按层打印是通过queue实现的了，正好复习一遍。
时间复杂度O(n)
空间复杂度O(n)

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root == null) return null;
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node != null){
                queue.offer(node.left);
                queue.offer(node.right);
                sb.append(node.val);
                sb.append(",");
            } else {
                sb.append("null,");
            }
        }
        return sb.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() == 0) return null;
        Queue<TreeNode> queue = new LinkedList<>();
        String[] arr = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(arr[0]));
        queue.offer(root);
        int i = 1;
        while(!queue.isEmpty()){
            TreeNode tmp = queue.poll();
            if(!arr[i].equals("null")){
                TreeNode left = new TreeNode(Integer.parseInt(arr[i]));
                tmp.left = left;
                queue.offer(left);
            }
            i++;
            if(!arr[i].equals("null")){
                TreeNode right = new TreeNode(Integer.parseInt(arr[i]));
                tmp.right = right;
                queue.offer(right);
            }
            i++;
        }
        return root;
    }
}

0 赞同 0 条回复

行动派小彩笔普通 2023年7月1日上午10:07

//时间复杂度O(n),空间复杂度O(n)
class Codec {
public:
    string s;
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root) return "";
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            TreeNode* tmp = q.front();
            q.pop();
            if(tmp)
            {
                q.push(tmp->left);
                q.push(tmp->right);
                s.append(to_string(tmp->val));
            }
            else
            {
                s.append("#");
            }
            s.append(",");
        }
        // s =  s.substr(0,s.size()-1);
        // for(int i=0;i<s.size();i++)
        // {
        //     cout<< s[i]<<" ";
        // }
        // cout<<endl;
        return s.substr(0,s.size()-1);

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
      if(data.size()==0)return NULL;
      vector<TreeNode*> v;
      int len = data.size();
      int i =0;
      while(i<len)
      {
          string s = "";
          while(data[i]!=','&&i<len)
          {
              s.push_back(data[i]);
              ++i;
          }
          if( s=="#")
          {
              v.push_back(NULL);
          }
          else
          {
              int x = stoi(s);
              TreeNode* tmp = new TreeNode(x);
              v.push_back(tmp);
          }
            ++i;
      }
      int j = 1;
      for(int i =0;j<v.size();i++)
      {
          if(v[i]==NULL) continue;
          if(j<v.size()) v[i]->left = v[j++];
          if(j<v.size()) v[i]->right = v[j++];
      }
    return v[0];

    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月1日上午9:14

遍历+字符串相关操作。

public String serialize(TreeNode root) {
        dfs(root);
        return sb.toString();
    }

    private void dfs(TreeNode node){
        if(node == null){
            sb.append("None,");
            return; 
        }
        sb.append(node.val + ",");
        dfs(node.left);
        dfs(node.right);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
         List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return deserialize(dataList);
    }

    private TreeNode deserialize(List<String> dataList){
        String data = dataList.get(0);
        dataList.remove(0);
        if(data.equals("None")){
            return null;
        }
        TreeNode node = new TreeNode(Integer.valueOf(data));
        node.left = deserialize(dataList);
        node.right = deserialize(dataList);
        return node;
    }

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月1日上午2:03

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """

        if not root:
            return ""

        q = [root]
        res = []

        while q:
            node = q.pop(0)
            if node:
                res.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                res.append("null")

        # print(",".join(res))

        return ",".join(res)


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

        :type data: str
        :rtype: TreeNode
        """

        if not data:
            return None

        nodes = data.split(",")
        # print(nodes)
        root = TreeNode(nodes[0])
        q = [root]
        i = 1

        while q:
            node = q.pop(0)
            # print(i)
            if nodes[i] != "null":
                node.left = TreeNode(nodes[i])
                q.append(node.left)
            i += 1
            if nodes[i] != "null":
                node.right = TreeNode(nodes[i])
                q.append(node.right)
            i += 1

        return root


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

使用null indicate the leaf node

0 赞同 0 条回复

伏月三十普通 2023年6月30日下午9:54

public class Codec {

    // Encodes a tree to a single string. 序列化二叉树 使用层序遍历 弄成一个字符串
    public String serialize(TreeNode root) {
        if(root==null){
            return "";
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        StringBuilder s=new StringBuilder();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            if(node!=null){
                queue.offer(node.left);
                queue.offer(node.right);
                s.append(node.val+",");
            }else{
                s.append("null,");
            }
        }
        return s.toString();
    }

    // Decodes your encoded data to tree.  把字符串用逗号分开  也用队列(队列里还是结点)  结点里还是int数值
    public TreeNode deserialize(String data) {
        if(data==null || data.length()<=0){
            return null;
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        String[] sArray=data.split(","); //分割成字符串数组
        TreeNode root=new TreeNode(Integer.parseInt(sArray[0]));
        queue.offer(root);//把头节点加到队列中
        int i=1;
        while(!queue.isEmpty()){
            TreeNode t=queue.poll();
            //构建左子节点  如果是null  直接就i++ 看下一个
            if(!sArray[i].equals("null")){
                TreeNode left=new TreeNode(Integer.parseInt(sArray[i]));//先把这个节点创建出来再连接
                t.left=left;
                queue.offer(left);
            }
            i++;
            //构建右子节点
            if(!sArray[i].equals("null")){
                TreeNode right=new TreeNode(Integer.parseInt(sArray[i]));//先把这个节点创建出来再连接
                t.right=right;
                queue.offer(right);
            }
            i++;
        }
        return root;

    }
}

看了视频照着写才会哈哈

0 赞同 0 条回复

yxy 普通 2023年6月30日下午9:23

复杂度O（n）
class Codec {
public:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
    if ( root == nullptr ) return "";
    ostringstream output;
    queue<TreeNode*> que;
    que.push(root);
    while ( !que.empty() ) {
        TreeNode* node = que.front();
        que.pop();
        if ( node == nullptr ) output << "# ";
        else {
            output << node->val << ' ';
            que.push(node->left);
            que.push(node->right);
        }
    }
    return output.str();
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
    if ( data.empty() ) return nullptr;
    vector<TreeNode*> nodes;
    string val;
    istringstream input(data);
    while ( input >> val ) {
        if ( val == "#" ) nodes.push_back(nullptr);
        else nodes.push_back(new TreeNode(stoi(val)));
    };
    int pos = 0;
    for ( int i = 0; i < nodes.size(); ++i ) {
        if ( nodes[i] == nullptr ) continue;
        nodes[i]->left = nodes[++pos];
        nodes[i]->right = nodes[++pos];
    }
    return nodes[0];
}

};

0 赞同 0 条回复

Ming 普通 2023年6月30日下午8:30

看了帅地讲解后就通了：
一个将二叉树转换成线性表的方法
一个将线性表转换成二叉树的方法
不过这里的线性表是带逗号的字符串

/**
 * 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.
    public String serialize(TreeNode root) {
        if(root == null) {
            return "";
        }
        StringBuilder build = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node != null) {
                q.offer(node.left);
                q.offer(node.right);
                build.append(node.val + ",");
            } else {
                build.append("null,");
            }
        }
        return build.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || data.length() <= 0){
            return null;
        }
        String[] s = data.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(s[0]));
        queue.offer(root);
        int i = 1;
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            //构建左子树，排出null
            if(!s[i].equals("null")) {
                TreeNode left = new TreeNode(Integer.parseInt(s[i]));
                cur.left = left;
                queue.offer(left);
            }
            i++;
            //构建右子树，排出null
            if(!s[i].equals("null")) {
                TreeNode right = new TreeNode(Integer.parseInt(s[i]));
                cur.right = right;
                queue.offer(right);
            }
            i++;
        }
        return root;
    }
}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月30日下午8:29

//思路：层序遍历，空结点也是孩子，也要存储
//时间O(n) 空间O(n)
public class Codec {

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

        StringBuffer result = new StringBuffer();
        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);

        while(!queue.isEmpty()){

            root = queue.poll();
            if(root != null){
                result.append(root.val+",");
                queue.offer(root.left);
                queue.offer(root.right);
            }else{
                result.append("#,");
            }       
        }

        return result.toString();

    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data == null || "".equals(data)){
            return null;
        }

        String[] values = data.split(",");
        Queue<TreeNode> queue = new LinkedList();
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        queue.offer(root);
        int index = 1;

        while(!queue.isEmpty()){

            TreeNode curRoot = queue.poll();

            if(!"#".equals(values[index])){
                curRoot.left = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(curRoot.left);
            }
            index++;
            if(!"#".equals(values[index])){
                curRoot.right = new TreeNode(Integer.parseInt(values[index]));
                queue.offer(curRoot.right);
            }
            index++;
        }

        return root;
    }
}

0 赞同 0 条回复

Dsjh 普通 2023年6月30日下午5:28

MY

// 层序遍历

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(!root){
            return "";
        }
        string ans;
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty()){
            int size = q.size();
            while(size--){
                TreeNode* temp = q.front();
                q.pop_front();
                if(temp){
                    string s = to_string(temp->val);               
                    ans+=s+',';
                    q.push_back(temp->left);
                    q.push_back(temp->right);
                }
                else{
                    ans += "#,";
                }
            }
        }
        return ans;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data.empty())
            return nullptr;
        // 将 各节点的值 放入 v
        vector<string> v;
        string s;
        for(auto& c :data){
            if(c == ','){
                v.push_back(s);
                s.clear();
            }
            else{
                s += c;
            }
        }
        if(s.size()!=0){
            v.push_back(s);
            s.clear();
        }

        // 层序遍历的方式重建
        TreeNode* root = new TreeNode(stoi(v.front()));
        v.erase(v.begin());
        deque<TreeNode*> q;
        q.push_back(root);
        while(!q.empty()){
            int size = q.size();
            for(int i=0;i<size;i++){
                TreeNode* temp = q.front();
                q.pop_front();
                if(v.front() != "#"){
                    TreeNode* l = new TreeNode(stoi(v.front()));
                    temp->left = l;
                    q.push_back(l);
                }
                v.erase(v.begin());
                if(v.front() != "#"){
                    TreeNode* r = new TreeNode(stoi(v.front()));
                    temp->right = r;
                    q.push_back(r);
                }
                v.erase(v.begin());

            }
        }
        return root;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年6月30日下午5:28

C++实现
时间复杂度和空间复杂度：O(n)

#include 
#include 
#include 

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 序列化二叉树
std::string serialize(TreeNode* root) {
    if (root == nullptr) {
        return "#";
    }
    std::string left = serialize(root->left);
    std::string right = serialize(root->right);
    return std::to_string(root->val) + "," + left + "," + right;
}

// 反序列化二叉树
TreeNode* deserializeHelper(std::istringstream& iss) {
    std::string str;
    std::getline(iss, str, ',');
    if (str == "#") {
        return nullptr;
    }
    int val = std::stoi(str);
    TreeNode* root = new TreeNode(val);
    root->left = deserializeHelper(iss);
    root->right = deserializeHelper(iss);
    return root;
}

TreeNode* deserialize(std::string data) {
    std::istringstream iss(data);
    return deserializeHelper(iss);
}

int main() {
    // 构建二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->right->left = new TreeNode(4);
    root->right->right = new TreeNode(5);

    // 序列化二叉树
    std::string serialized = serialize(root);
    std::cout << "Serialized binary tree: " << serialized << std::endl;

    // 反序列化二叉树
    TreeNode* deserialized = deserialize(serialized);
    std::cout << "Deserialized binary tree: " << std::endl;
    std::cout << "       " << deserialized->val << std::endl;
    std::cout << "      / \\" << std::endl;
    std::cout << "     " << deserialized->left->val << "   " << deserialized->right->val << std::endl;
    std::cout << "          / \\" << std::endl;
    std::cout << "         " << deserialized->right->left->val << "   " << deserialized->right->right->val << std::endl;

    // 释放内存
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

0 赞同 0 条回复

Yodl. 普通 2023年6月30日下午4:30

class Codec 
{
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) 
    {
        if(root == nullptr)
            return "";
        string res;
        queue<TreeNode* > my_queue;
        my_queue.push(root);
        while(!my_queue.empty())
        {
            TreeNode* tmp = my_queue.front();
            my_queue.pop();
            if(tmp == nullptr)
            {
                res.push_back('#');
                res += ',';
            }
            else
            {
                res.append(to_string(tmp->val));
                res += ',';
                my_queue.push(tmp->left);
                my_queue.push(tmp->right);
            }
        }
        //cout << res << endl;
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) 
    {
        if(data.size() == 0)
            return nullptr;
        vector<TreeNode* > nodes;
        int j = 0;
        while(j < data.size())
        {
            string stmp = "";
            while(data[j] != ',')
            {
                stmp += data[j];
                j++;
            }

            if(stmp == "#")
            {
                nodes.push_back(nullptr);
            }
            else
            {
                int tmp = atoi(stmp.c_str());
                TreeNode* newnode = new TreeNode(tmp);
                nodes.push_back(newnode);
            }
            j++;
        }
        int pos = 1;
        for(int i = 0; i < nodes.size(); ++i)
        {
            if(nodes[i] == nullptr)
                continue;
            nodes[i]->left = nodes[pos++];
            nodes[i]->right = nodes[pos++];
        }

        return nodes[0];
    }
};
//时间复杂度：O(n)
//空间复杂度：O(n)

0 赞同 0 条回复

张开怀普通 2023年6月30日下午4:05

class Codec{
public:
       string serialize(TreeNode* root){
               if(root == nullptr){
                      return "";
               }
               stringstream ss;
               queze<TreeNode*> q{{root}};
               while(!q.empty()){
                      int n = q.size();
                      for(int i=0;i<n;i++){
                             auto t=q.front();
                             q.pop();
                             if(t){
                                    ss<<t->val<<",";
                                    q.push(t->left);
                                    q.push(t->right);
                             }else{
                                    ss<<"null,";
                             }
                      }
               }
               string str == ss.str();
               return str.substr(0,str.length()-1);
       }
       TreeNode* deserialize(string data){
              if(data.empty()){
                     return nullptr;
              }
              vector<string> nodes;
              stringstream ssin(data);
              string token;
              while(getline(ssin,token,',')){
                     nodes.push_back(token);
              }
              TreeNode* root = new TreeNode(atoi(nodes[0].c_str()));
              queue<TreeNode*> q{{root}};
               int i=1;
               while(!q.empty() && i<nodes.size()){
                      auto t=q.front();
                      q.pop();
                      if(nodes[i] != "null"){
                             t->left = new TreeNode(atoi(nodes[i].c_str()));
                             q.push(t->right);
                      }
                      i++;
               }
               return root;
       }
};

时间复杂度：O(n)
空间复杂度：O(2n)近似O(n)

0 赞同 0 条回复

【二叉树专题】剑指 Offer 37. 序列化二叉树

共以下 26 个回答

MY

# 回答此问题取消回复

【二叉树专题】剑指 Offer 37. 序列化二叉树

共以下 26 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复