leetcode-pp / 91alg-6-daily-check

91 算法第六期打卡仓库

28 stars 0 forks source link

【Day 17 】2021-12-28 - 297. 二叉树的序列化与反序列化 #24

Open azl397985856 opened 2 years ago

azl397985856 commented 2 years ago

297. 二叉树的序列化与反序列化

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

前置知识

暂无

题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例: 

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

wxj783428795 commented 2 years ago

思路

dfs，前序遍历
序列化时，将当前节点值并入字符串，用‘，’隔开，null也是
反序列化时，将字符串从'，'处隔开，数组的第一个值就是当前节点，第二个值是当前节点的左侧子节点，第三个值就是右侧
递归即可

代码


/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
    let str = "";
    var dfs = function (root) {
        if (!root) {
            str += ",null";
            return;
        }
        str += `,${root.val}`;
        dfs(root.left);
        dfs(root.right);
    };
    dfs(root);
    return str.slice(1);
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
    let list = data.split(",");
    var dfs = function (str) {
        if (str[0] === "null") {
            str.shift();
            return null;
        }
        let node = new TreeNode(str[0]);
        str.shift();
        node.left = dfs(str);
        node.right = dfs(str);
        return node;
    };
    return dfs(list);
};

复杂度分析

复杂度分析不是很会，不一定对，如果有错，请指正。

时间复杂度：O(n)
空间复杂度：O(h)

pengfeichencpf commented 2 years ago

class Codec { public: // Encodes a tree to a single string. string serialize(TreeNode root) { ostringstream out; serialize(root, out); return out.str(); } // Decodes your encoded data to tree. TreeNode deserialize(string data) { istringstream in(data); return deserialize(in); } private: void serialize(TreeNode root, ostringstream &out) { if (root) { out << root->val << ' '; serialize(root->left, out); serialize(root->right, out); } else { out << "# "; } } TreeNode deserialize(istringstream &in) { string val; in >> val; if (val == "#") return nullptr; TreeNode *root = new TreeNode(stoi(val)); root->left = deserialize(in); root->right = deserialize(in); return root; } };

Hawkins-hjq commented 2 years ago

public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

caohaha commented 2 years ago

python程序

# 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 = [[0,-1,'L',root]]
        i = 1
        # 层次遍历
        for t in q:
            p,_,_,node = t
            if node.left:
                q.append([i,p,'L',node.left])
                i += 1
            if node.right:
                q.append([i,p,'R',node.right])
                i += 1
        # 将节点转换为对应的值
        def converToStr(t):
            t[3] = t[3].val

            return ','.join(str(x) for x in t)
        q = [converToStr(t) for t in q]

        return '+'.join(q)

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        data = data.split('+')
        maps = {}
        root = None
        for t in data:
            i,p,direction,val = t.split(',')
            node = TreeNode(int(val))
            if i == '0':
                root = node
            maps[i] = node
            if p in maps:
                # 父节点存在 跟新指向关系
                parent = maps[p]
                if direction == 'L':
                    parent.left = node
                else:
                    parent.right = node
        return root

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

时间复杂度O(n)
空间复杂度O(n)

guoling0019 commented 2 years ago

关键点

前序遍历

代码

语言支持：JavaScript

JavaScript Code:


/**
 * 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) {
    if(root==null){
        return 'null'
    }
    const left=serialize(root.left)
    const right=serialize(root.right)
    return root.val+','+left+','+right
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const list = data.split(',')
    const buildTree=(list)=>{
        const rootVal=list.shift()
        if(rootVal=="null"){
            return null
        }
        const root=new TreeNode(rootVal)
        root.left=buildTree(list)
        root.right=buildTree(list)
        return root
    }
    return buildTree(list)
};

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

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(n)$

xiao-xiao-meng-xiang-jia commented 2 years ago

public class Codec { public String serialize(TreeNode root) { if (root == null) { return "X"; } String left = "(" + serialize(root.left) + ")"; String right = "(" + serialize(root.right) + ")"; return left + root.val + right; }

public TreeNode deserialize(String data) {
    int[] ptr = {0};
    return parse(data, ptr);
}

public TreeNode parse(String data, int[] ptr) {
    if (data.charAt(ptr[0]) == 'X') {
        ++ptr[0];
        return null;
    }
    TreeNode cur = new TreeNode(0);
    cur.left = parseSubtree(data, ptr);
    cur.val = parseInt(data, ptr);
    cur.right = parseSubtree(data, ptr);
    return cur;
}

public TreeNode parseSubtree(String data, int[] ptr) {
    ++ptr[0]; // 跳过左括号
    TreeNode subtree = parse(data, ptr);
    ++ptr[0]; // 跳过右括号
    return subtree;
}

public int parseInt(String data, int[] ptr) {
    int x = 0, sgn = 1;
    if (!Character.isDigit(data.charAt(ptr[0]))) {
        sgn = -1;
        ++ptr[0];
    }
    while (Character.isDigit(data.charAt(ptr[0]))) {
        x = x * 10 + data.charAt(ptr[0]++) - '0';
    }
    return x * sgn;
}

}

wenlong201807 commented 2 years ago

代码块


// /**
//  * Encodes a tree to a single string.
//  *
//  * @param {TreeNode} root
//  * @return {string}
//  */
var serialize = function (root) {
  if (root === null) {
    return root;
  }
  const result = [];
  const queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      queue.push(node.left);
      queue.push(node.right);
    }
    result.push(node ? node.val : null);
  }
  return result.join(",");
};

//       1
//   2      3
// 4   5

// r: 1,2,3,4,5,null,null,null,null,null,null
// q: 
/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  if (!data) {
    return null;
  }
  let serializeList = data.split(",");
  const val = serializeList.shift()
  let root = new TreeNode(val);
  let queue = [root];
  while (queue.length) {
    const node = queue.shift();
    if (node) {
      const leftVal = serializeList.shift();
      const rightVal = serializeList.shift();
      node.left = leftVal ? { val: leftVal } : null;
      node.right = rightVal ? { val: rightVal } : null;
      queue.push(node.left);
      queue.push(node.right);
    }
  }
  return root;
};

时间复杂度和空间复杂度

时间复杂度 O(n)
空间复杂度 O(1)

chenyaohn commented 2 years ago

思路

层序遍历（bfs）

代码

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 ArrayDeque<>();
            queue.offer(root);
            TreeNode temp = new TreeNode();
            while (!queue.isEmpty()){
                int size = queue.size();
                while (size>0){
                    TreeNode node = queue.poll();
                    if(node==temp)
                        sb.append(null+",");
                    else{
                        sb.append(node.val+",");
                        queue.offer(node.left!=null?node.left:temp);
                        queue.offer(node.right!=null?node.right:temp);
                    }
                    size--;
                }
            }
            sb.replace(sb.length()-1,sb.length(),"]");
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            Queue<String> nodeQueue = decodeValue(data);
            String root = nodeQueue.poll();
            if("null".equals(root)){
                return null;
            }
            Queue<TreeNode> queue = new ArrayDeque<>();
            TreeNode rootNode = new TreeNode(Integer.parseInt(root));
            TreeNode temp = new TreeNode();
            queue.offer(rootNode);
            while (!nodeQueue.isEmpty()){
                int len = queue.size();

                while (len>0&&!nodeQueue.isEmpty()){
                    TreeNode node = queue.poll();
                    String left = nodeQueue.poll();
                    String right = nodeQueue.poll();
                   // System.out.println("node:"+node.val+",l:"+left+",r:"+right);
                    if("null".equals(left)){//left必不为空，否则nodeQueue为空，无法进入循环
                        node.left = null;
                    }else{
                        node.left = new TreeNode(Integer.parseInt(left));
                        queue.offer(node.left);
                    }
                    if(null!=right && "null".equals(right)){
                        node.right = null;
                    }else if(null!=right && !"null".equals(right)){
                        node.right = new TreeNode(Integer.parseInt(right));
                        queue.offer(node.right);
                    }
                    len--;
                }
            }
            return rootNode;
        }

        public static Queue<String>  decodeValue(String data){
            Queue<String> node = new ArrayDeque<>();
            int i =1;
            String str = "";
            while (i<data.length()){
                if(data.charAt(i)!=','&&data.charAt(i)!=']'){
                    str+=data.charAt(i);
                }else {
                    node.offer(str.toString());
                    str="";
                }
                i++;
            }
            return node;
        }
    }
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

jiaqiliu37 commented 2 years ago

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        def dfs(node):
            if not node:
                return 'None,'
            else: 
                return str(node.val) + ',' + dfs(node.left) + dfs(node.right)

        return dfs(root)

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

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

        def dfs(data_list):
            if data_list[0] == 'None':
                data_list.pop(0)
                return None

            node = TreeNode(int(data_list[0]))
            data_list.pop(0)
            node.left = dfs(data_list)
            node.right = dfs(data_list)
            return node

        data_list = data.split(',')
        return dfs(data_list)

Time complexity O(n) Space complexity O(h)

rzhao010 commented 2 years ago

Thoughts

Tree manipulating & Pre-traversing Find root first then compose/decompose both left & righjt branches

Code

public class Codec {

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

    // 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 redeserialize(dataList);
    }

    private String reserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = reserialize(root.left, str);
            str = reserialize(root.right, str);
        }
        return str;
    }

    private TreeNode redeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        } 

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = redeserialize(dataList);
        root.right = redeserialize(dataList);

        return root;
    }
}

Complexity

Time: O(n)
Space: O(n)

aladingzl commented 2 years ago

思路

代码

var serialize = function(root) {
    if(root === null) {
        return 'X';
    }
    const left = serialize(root.left);
    const right = serialize(root.right);
    return root.val + ',' + left + ',' + right;
};

var deserialize = function(data) {
    const list = data.split(',');

    const buildTree = (list) => {
        const rootVal = list.shift();
        if(rootVal === 'X') {
            return null;
        }
        const root = new TreeNode(rootVal);
        root.left = buildTree(list);
        root.right = buildTree(list);
        return root;
    }
    return buildTree(list);
};

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

复杂度分析

时间复杂度：O(N)
空间复杂度：O(N)

Flower-F commented 2 years ago

解题思路

DFS。选择前序遍历，这样更容易确认根节点的位置。

代码

/**
 * 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) {
    if (root === null) {
        return 'N';
    }
    const left = serialize(root.left);
    const right = serialize(root.right);

    // 选择前序遍历，是因为这样在反序列化时更容易定位根节点
    return root.val + ',' + left + ',' +  right;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    const list = data.split(',');
    return dfs(list);

    function dfs(list) {
        // 先序遍历，所以第一项就是根
        const rootVal = list.shift(); 
        // 特判
        if (rootVal === 'N') {
            return null;
        }

        // 创建根节点
        const root = new TreeNode(rootVal); 
        root.left = dfs(list);
        root.right = dfs(list);
        return root;
    }
};

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

复杂度

时间：O(N) 空间：O(N)

declan92 commented 2 years ago

第一反应：前序遍历对树进行编码;
思路:
序列化:前序遍历树,每个结点之间使用","分隔,左右子树为空,使用"null"补全;
反序列化:使用","将字符串解析成数组,先解析根节点,然后左子树,最后右子树;
java

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        String ans = preOrder(root,"");
        //remove ","
        return ans.substring(0,ans.length()-1);
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] array = data.split(",");
        LinkedList<String> list = new LinkedList(Arrays.asList(array));
        if(list.get(0).equals("null")){
            return null;
        }
        //TreeNode ans = new TreeNode(Integer.valueOf(list.get(0)));

        return des(list);
    }
    public TreeNode des(LinkedList<String> list){
        String val = list.remove(0);
        if(val.equals("null")){
            return null;
        }else{
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = des(list);
            node.right = des(list);
            return node;
        }
    }    
    public String preOrder(TreeNode root,String str){
        if(root == null){
            return str += "null,";
        }
        str += root.val + ",";
        str = preOrder(root.left,str);
        str = preOrder(root.right,str);
        return str;
    }
}

时间:O(n),n为树的长度;
空间:O(n),最坏情况树的高度等于层数

Serena9 commented 2 years ago

代码

class Codec:
    def serialize(self, root):
        def preorder(root):
            if not root:
                return "null,"
            return str(root.val) + "," + preorder(root.left) + preorder(root.right)

        return preorder(root)[:-1]

    def deserialize(self, data: str):
        nodes = data.split(",")

        def preorder(i):
            if i >= len(nodes) or nodes[i] == "null":
                return i, None
            root = TreeNode(nodes[i])
            j, root.left = preorder(i + 1)
            k, root.right = preorder(j + 1)
            return k, root

        return preorder(0)[1]

falconruo commented 2 years ago

思路:

复杂度分析:

时间复杂度: O(n), n为树的节点数
空间复杂度: DFS O(logn), BFS: O(n), n为树的节点数

代码(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:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if (!root) return "";
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }
private:
    void serialize(TreeNode* root, ostringstream& out) {
        if (!root) {
            out << ",null";
            return;
        }

        out << root->val << ',';
        serialize(root->left, out);
        serialize(root->right, out);
    }

    TreeNode* deserialize(istringstream& in) {
        string val;
        getline(in, val, ',');
        if (val == "null") return NULL;

        TreeNode* root = new TreeNode(stoi(val));
        root->left = deserialize(in);
        root->right = deserialize(in);
        return root;
    }
};

watchpoints commented 2 years ago

思路

非递归遍历，当然递归更加方便。

代码

/**
 * 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) {
        queue<TreeNode*> q;
        q.push(root);
        string str;
        while(q.size()){
            TreeNode* t=q.front();
            q.pop();
            if(t)str+=to_string(t->val)+" ";
            else{
                str+="* ";
                continue;
            }
            q.push(t->left);
            q.push(t->right);
        }
        //cout<<str;
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        stringstream ss;
        ss<<data;
        string str1,str2;
        ss>>str1;
        if(str1=="*")return NULL;
        TreeNode* root=new TreeNode(stoi(str1));
        queue<TreeNode*> q;
        q.push(root);
        while(ss>>str1){
            if(!(ss>>str2))break;
            TreeNode* t=q.front();
            q.pop();
            if(str1=="*")t->left=NULL;
            else{
                TreeNode* node=new TreeNode(stoi(str1));
                t->left=node;
                q.push(node);
            }
            if(str2=="*")t->right=NULL;
            else{
                TreeNode* node=new TreeNode(stoi(str2));
                t->right=node;
                q.push(node);
            }
        }
        return root;
    }
};

samaritan1998 commented 2 years ago

二叉树的序列化和反序列化

from collections import deque
class Codec:
    def serialize(self, root):
        if root == None: return 'X,'
        leftserilized = self.serialize(root.left)
        rightserilized = self.serialize(root.right)
        return str(root.val) + ',' + leftserilized + rightserilized

    def deserialize(self, data):
        data = data.split(',') #先转换为数组  
        root = self.buildTree(data)
        return root 

    def buildTree(self,data):
        val = data.pop(0)
        if val == 'X': return None  #弹出最左节点
        node = TreeNode(val)
        node.left = self.buildTree(data)  #深度优先遍历
        node.right = self.buildTree(data)  #这时传进入的data是没有左节点的
        return node

Tiquiero commented 2 years ago

const serialize = (root) => {
  if (root == null)  return 'X';
  const left = serialize(root.left);   // 左子树的序列化结果
  const right = serialize(root.right); // 右子树的序列化结果
  return root.val + ',' + left + ','+ right; // 按  根,左,右  拼接字符串
};

const deserialize = (data) => {
  const list = data.split(',');   // split成数组
  const buildTree = (list) => {   // 基于list构建当前子树
    const rootVal = list.shift(); // 弹出首项，获取它的“数据”
    if (rootVal == "X") return null;
    const root = new TreeNode(rootVal); // 不是X，则创建节点
    root.left = buildTree(list);        // 递归构建左子树
    root.right = buildTree(list);       // 递归构建右子树
    return root;                        // 返回当前构建好的root
  };

  return buildTree(list); // 构建的入口
};

callmeerika commented 2 years ago

思路

利用广度遍历

代码

var serialize = function(root) {
    let queue = [];
    let queue1 = [];
    let queue2 = [];
    if(!root || root.val === null) return JSON.stringify(queue);
    queue.push(root.val);
    queue1.push(root)
    while (queue1.length) {
        let ele = queue1.shift();
        if(ele !== null){
            queue.push(ele.left ? ele.left.val : ele.left);
            queue.push(ele.right? ele.right.val : ele.right);
            queue2.push(ele.left);
            queue2.push(ele.right);
        }
        if(!queue1.length) {
        queue1 = queue2;
        queue2 = [];
        }
    }
    for(let i = queue.length - 1;i>0;i--){
        if(queue[i]===null) {
        queue.pop();
        } else {
        break;
        }
    }
    return JSON.stringify(queue);
};
var deserialize = function(data) {
    let arr = JSON.parse(data);
    if(arr.length === 0) return null;
    let root = new TreeNode(arr.shift());
    let queue1 = [root];
    let queue2 = [];
    while(queue1.length&&arr.length) {
        let ele = queue1.shift();
        let left = arr.shift()
        let right = arr.shift()
        if(left !== null) {
            ele.left = new TreeNode(left);
            queue2.push(ele.left);
        }
        if(right !== null && right !== undefined) {
            ele.right = new TreeNode(right);
            queue2.push(ele.right);
        }
        if(!queue1.length) {
            queue1 = queue2;
            queue2 = [];
        }
    }
    return root
};

复杂度

时间复杂度：O(n)
空间复杂度：O(n)

ZJP1483469269 commented 2 years ago

public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return "null";
        return root.val+","+serialize(root.left)+","+serialize(root.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));
        TreeNode root =  rdeserialize(dataList);
        return root;
    }

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

}

phybrain commented 2 years ago

思路

递归

代码


class Codec:
    def serialize(self, root):
        def preorder(root):
            if not root:
                return "null,"
            return str(root.val) + "," + preorder(root.left) + preorder(root.right)

        return preorder(root)[:-1]

    def deserialize(self, data: str):
        nodes = data.split(",")

        def preorder(i):
            if i >= len(nodes) or nodes[i] == "null":
                return i, None
            root = TreeNode(nodes[i])
            j, root.left = preorder(i + 1)
            k, root.right = preorder(j + 1)
            return k, root

        return preorder(0)[1]

复杂度分析

时间复杂度：O(N)，其中 N 为数组长度。
空间复杂度：O(H)

Alfie100 commented 2 years ago

二叉树的前序遍历、后序遍历、层序遍历

LeetCode题目连接： 297. 二叉树的序列化与反序列化 https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

解题思路

典型的二叉树遍历问题。不同于常规的二叉树遍历，如【LeetCode 144. 二叉树的前序遍历】、【145. 二叉树的后序遍历】，本题需要自行设计序列 / 反序列化的输入和输出格式。
序列化函数将TreeNode类型序列化为str，而反序列化函数将str转化为TreeNode类型。在序列化的过程中，当遍历到的节点不存在时（为null），也需要返回对应的null以便后续进行反序列化。为方便标记，我们可将null返回并表示为字符串'null'。
本题采用 前序遍历、后序遍历 和 层序遍历 的方式可较为直观地达成目标。下面给出几种写法：

深度优先 DFS ：前序遍历、后序遍历
广度优先 BFS ：层序遍历

TreeNode 类型

TreeNode 在初始化时已将 left 和 right 子节点设为 None。

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

1. 深度优先 DFS ：前序遍历

class Codec:
    # 前序遍历
    def serialize(self, root: TreeNode) -> str:
        # 常规的dfs前序遍历，注意return返回的类型即可
        def dfs(root):
            if not root:
                return 'null'
            return str(root.val) +','+ str(dfs(root.left)) +','+ str(dfs(root.right))
        return dfs(root)

    def deserialize(self, data: str) -> TreeNode:
        def buildTree(data):
            val = data.popleft()    # 使用deque.popleft()可加快运算，而常规的stack.pop(0)则较慢
            if val == 'null':
                return None
            root = TreeNode(val)    # 在前序遍历中，第一个节点即为当前（子）树的根节点
            root.left = buildTree(data)     # 前序遍历，先访问left子节点
            root.right = buildTree(data)
            return root
        #
        data = collections.deque(data.split(','))   # 使用双端队列
        return buildTree(data)

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。
空间复杂度：$O(n)$，最坏情况下可达$O(n)$。

2. 深度优先 DFS ：后序遍历

将前序遍历中的节点访问顺序稍作修改，即可达成后序遍历。

class Codec:
    # 后序遍历
    def serialize(self, root: TreeNode) -> str:
        # 常规的dfs前序遍历，注意return返回的类型即可
        def dfs(root):
            if not root:
                return 'null'
            return str(dfs(root.left)) +','+ str(dfs(root.right)) +','+ str(root.val)
        return dfs(root)

    def deserialize(self, data: str) -> TreeNode:
        def buildTree(data):
            val = data.pop()    # 在后序遍历中，可利用栈的特点，第一个弹出的节点即为当前（子）树的根节点
            if val == 'null':
                return None
            root = TreeNode(val)
            root.right = buildTree(data)
            root.left = buildTree(data)
            return root
        #
        data = data.split(',')
        return buildTree(data)

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。
空间复杂度：$O(n)$，最坏情况下可达$O(n)$。

3. 广度优先 BFS ：层序遍历

层序遍历使用 广度优先搜索 较为直观。

class Codec:
    # 层序遍历：bfs
    def serialize(self, root: TreeNode) -> str:
        if not root:
            return 'null'
        res = []
        deque = collections.deque([root])
        while deque:
            node = deque.popleft()
            if not node:        # 节点不存在，需表示为'null'
                res.append('null')
            else:               # 节点存在，将其值加入结果中，并将其左右子节点加入队列中
                res.append(str(node.val))
                deque.append(node.left)
                deque.append(node.right)
        return ','.join(res)

    def deserialize(self, data: str) -> TreeNode:
        data = data.split(',')
        if not data or data[0] == 'null':
            return None
        # 根节点root
        root = TreeNode(data[0])
        deque = collections.deque([root])
        n = len(data)
        for i in range(1, n, 2):    # 每次添加左右两个子节点
            node = deque.popleft()
            left_val = data[i]
            right_val = data[i+1]   # 序列化后的格式需保证左右子节点同时有表示（哪怕为'null'），否则data[i+1]有可能超出范围
            #
            if left_val != 'null':
                left_node = TreeNode(left_val)
                node.left = left_node
                deque.append(left_node)
            #
            if right_val != 'null':
                right_node = TreeNode(right_val)
                node.right = right_node
                deque.append(right_node)

        return root

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。
空间复杂度：$O(n)$，最坏情况下可达$O(n)$。

Davont commented 2 years ago

code

 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    if(!root) return "['null']"
    let queue = [root]
    let res = []
    while(queue.length){
      let node = queue.shift()
      if(node){
        res.push(node.val)
        queue.push(node.left)
        queue.push(node.right)
      } else {
        res.push('null')
      }
    }
    return JSON.stringify(res)
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
  if(data === "['null']") return null
  let list = JSON.parse(data)
  let root = new TreeNode(list[0])
  let queue = [root]
  let i = 1
  while(queue.length){
    let node = queue.shift()
    let left = list[i]
    let right = list[i + 1]
    if(left !== 'null'){
      let l = new TreeNode(left)
      node.left = l
      queue.push(l)
    }
    if(right !== 'null'){
      let r = new TreeNode(right)
      node.right = r
      queue.push(r)
    }
    i += 2
  }
  return root
};

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

frgthyju commented 2 years ago

先序遍历

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil{
        return "x"
    }
    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 {    
   list := strings.Split(data,",")
   return buildTree(&list)
}

func buildTree(list *[]string) *TreeNode{
    rootVal := (*list)[0]
    (*list) = (*list)[1:]
    if rootVal == "x"{
        return nil
    }
    Val,_ := strconv.Atoi(rootVal)
    root := &TreeNode{
        Val:Val,
    }
    root.Left = buildTree(list)
    root.Right = buildTree(list)
    return root
}

时间复杂度O(n)

空间复杂度O(n)

stackvoid commented 2 years ago

思路

采用二叉树的层序遍历解题。 (1)serialize()函数部分：首先按照层序遍历的顺序把二叉树的各个节点的值存到列表elems里，然后将elems转换成字符串。由于有多次的字符串连接操作，为了提高效率，采用StringBuilder。要注意的是，对于空节点(null)，存到字符串里的是一个特殊标记"n"，表明这是一个空节点。同时要采用分隔符","，不然反序列化的时候无法区分每个数字。 (2)deserialize()函数部分：首先把字符串按照分隔符","进行分割，得到每一个节点的值(可能为"n"，表示该节点为空节点)，然后同样按照层序遍历的思路从根节点开始构造二叉树。最后返回二叉树的根节点。

代码

public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root==null){
            return null;
        }
        // 层序遍历
        Queue<TreeNode> q1 = new LinkedList<>();
        List<Integer> elems = new ArrayList<>();
        q1.add(root);
        TreeNode n;
        int layerWidth = 0;
        while (!q1.isEmpty()){
            layerWidth = q1.size(); // 当前所有父节点的所有子节点个数
            for (int i=0;i<layerWidth;i++){
                n = q1.poll();
                if (n!=null){
                    elems.add(n.val);
                    if (n.left!=null){
                        q1.add(n.left);
                    }
                    else{
                        q1.add(null);
                    }
                    if (n.right!=null){
                        q1.add(n.right);
                    }
                    else{
                        q1.add(null);
                    }
                }
                else{
                    elems.add(null);
                }
            }
        }
        int N = elems.size();
        // 多次连接，使用StringBuilder提高效率
        StringBuilder ans = new StringBuilder();
        for (int i=0;i<N;i++){
            if (elems.get(i)==null){
                ans.append("n,");
            }
            else{
                ans.append(elems.get(i).toString()+",");
            }
        }
        return ans.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data==null){
            return null;
        }
        // 层序遍历
        Queue<TreeNode> q1 = new LinkedList<>();
        String[] datas = data.split(",");
        int N = datas.length;
        TreeNode root = new TreeNode(Integer.parseInt(datas[0]));
        q1.add(root);
        for (int i=1;i<N;i++){
            TreeNode r = q1.poll();
            if (!datas[i].equals("n")){
                TreeNode newRoot1 = new TreeNode(Integer.parseInt(datas[i]));
                r.left = newRoot1;
                q1.add(newRoot1);
            }
            i++;
            if (!datas[i].equals("n")){
                TreeNode newRoot2 = new TreeNode(Integer.parseInt(datas[i]));
                r.right = newRoot2;
                q1.add(newRoot2);
            }
        }
        return root;
    }
}

复杂度分析

时间复杂度： O(N)

空间复杂度：O(N)

junbuer commented 2 years ago

思路

层次遍历二叉树，当遇到null时用X标识。之后根据层次遍历得到的二叉树的结构分层重新构建二叉树

代码

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""
        que = [root]
        data = []
        while que:
            node = que.pop(0)
            if node:
                data.append(str(node.val))
                que.append(node.left)
                que.append(node.right)
            else:
                data.append('X')
        return ','.join(data)

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        data = data.split(',')
        root = TreeNode(int(data[0]))
        que = [root]
        i = 1
        while que:
            node = que.pop(0)
            if data[i] != 'X':
                node.left = TreeNode(int(data[i]))
                que.append(node.left)
            i += 1

            if data[i] != 'X':
                node.right = TreeNode(int(data[i]))
                que.append(node.right)
            i += 1
        return root

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

732837590 commented 2 years ago

该题没啥思路，参考大佬的解法 public class Codec {

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

StringBuilder mySeri(TreeNode root,StringBuilder sb){
    if(root==null){
        sb.append("null,");
        return sb;
    }
    else if(root!=null){
        sb.append(root.val);
        sb.append(",");

        mySeri(root.left,sb);
        mySeri(root.right,sb);
    }
    return sb;
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    String []temp=data.split(","); // 将序列化的结果转为字符串数组
    List<String> list=new LinkedList<>(Arrays.asList(temp)); // 字符串数组转为集合类 便于操作
    return myDeSeri(list);
}

public TreeNode myDeSeri(List<String> list){
    TreeNode root;
    if(list.get(0).equals("null")){
        list.remove(0); // 删除第一个元素 则第二个元素成为新的首部 便于递归 
        return null;
    }
    else{
        root=new TreeNode(Integer.valueOf(list.get(0)));
        list.remove(0);
        root.left=myDeSeri(list);
        root.right=myDeSeri(list);
    }
    return root;
}

}

KevinWorkSpace commented 2 years ago

public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }
}

Macvh commented 2 years ago

class Codec:

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

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

    def bfs(root,a):
        queue=[]
        queue.append(root)
        while queue:
            forward=queue
            queue=[]
            f = 0
            for b in forward:
                if(b.val!="A"):
                    f = 1
                    break
            if(f==1):
                for i in forward:
                    if(i.val=='A'):
                        queue.append(TreeNode("A"))
                        queue.append(TreeNode("A"))
                        a = a + "N,"
                        a = a + "N,"
                        continue
                    if i.left:
                        queue.append(i.left)
                        a = a+ str(i.left.val)+','
                    if not i.left:
                        queue.append(TreeNode("A"))
                        a = a + "N,"
                    if i.right:
                        queue.append(i.right)
                        a = a + str(i.right.val)+','
                    if not i.right:
                        queue.append(TreeNode("A"))
                        a = a + "N,"

        return a
    if not root:
        return []
    a = str(root.val)+','
    a = bfs(root,a)
    return a

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

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

    def construct(root,data,i):
        if (root == None):
            return 

        if 2*i-1<len(data):
            if(data[2*i-1]=="N"):
                root.left = None
            else:
                root.left=TreeNode(data[2*i-1])
            construct(root.left,data,2*i)
        if 2*i<len(data):
            if(data[2*i]=="N"):
                root.right = None
            else:
                root.right=TreeNode(data[2*i])
            construct(root.right,data,2*i+1)

    if not data:
        return
    data = data.split(',')
    root=TreeNode(data[0])
    i=1
    construct(root,data,i)
    return root

lilililisa1998 commented 2 years ago

class Codec:

def serialize(self, root):
    if not root:
        return ""
    dq = deque([root])
    res = []
    while dq:
        node = dq.popleft()
        if node:
            res.append(str(node.val))
            dq.append(node.left)
            dq.append(node.right)
        else:
            res.append('None')
    return ','.join(res)

def deserialize(self, data):
    if not data:
        return []
    dataList = data.split(',')
    root = TreeNode(int(dataList[0]))
    dq = deque([root])
    i = 1
    while dq:
        node = dq.popleft()
        if dataList[i] != 'None':
            node.left = TreeNode(int(dataList[i]))
            dq.append(node.left)
        i += 1
        if dataList[i] != 'None':
            node.right = TreeNode(int(dataList[i]))
            dq.append(node.right)
        i += 1
    return root

Moin-Jer commented 2 years ago

思路

DFS

代码

public class Codec {
    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    public String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += "None,";
        } else {
            str += str.valueOf(root.val) + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }
}

复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)

CodeWithIris commented 2 years ago

Question

Day17 297 https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

Note

Using ostringstream and istringstream to input and output data.
In istringstream, spaces can be used as output delimiters without judgment.

Solution (C++)


class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }
private:
    void serialize(TreeNode* root, ostringstream& out) {
        if (root == nullptr) {
            out << "# ";
        }else{
            out << root->val << " ";
            serialize(root->left, out);
            serialize(root->right, out);
        }        
    }

    TreeNode* deserialize(istringstream& in) {
        string val;
        in >> val;
        if (val == "#") return nullptr;        
        TreeNode* root = new TreeNode(stoi(val));        
        root->left = deserialize(in);
        root->right = deserialize(in);        
        return root;
    }
};

Complexity

T: O(n): Traverse over the tree when 'serialize'.
S: O(n): The worst situation is O(n) if the binary tree degenerates into a chain.

ggohem commented 2 years ago

思路：

本质还是树的遍历，可以采用DFS解决。

DFS：
- 序列化(遍历一遍字符串记录树中节点值)：
- 遇见空节点，字符串加null,
- 遇见非空节点，字符串加上节点的值和用来间隔的逗号，再递归左右子树。
- 反序列化(将字符串进行解析，构造出对应的树)：
- 遍历字符串
  - 遇见null，返回空节点；
  - 遇见非null，将其值解析成整数，再构造根节点。递归构造根节点的左右子树。

序列化与反序列化的操作应该是互逆的，所以想法中的序列化用BFS，反序列化用DFS是不行的。

tips:

BFS有两种处理方式：入队时处理和出队时处理。

代码：

import java.util.Arrays;
import java.util.LinkedList;

/**
 * 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) {
        return dfsSer(root, "");
    }

    public String dfsSer(TreeNode root, String s) {
        if (root == null) s += "null,";
        else {
            s += root.val + ",";
            s = dfsSer(root.left, s); // 前面的+=已经是在前面的字符串上添加了，所以是=
            s = dfsSer(root.right, s);
        }
        return s;
    }

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

    public TreeNode dfsDeser(LinkedList<String> list) {
        if (!list.isEmpty() && list.get(0).equals("null")) {
            list.remove(0);
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(list.get(0)));
        list.remove(0);
        root.left = dfsDeser(list);
        root.right = dfsDeser(list);
        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));

时空复杂度：

时间复杂度：O(n)
空间复杂度：O(height)

ray-hr commented 2 years ago

代码

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""
        queue = collections.deque([root])
        res = []
        while queue:
            node = queue.popleft()
            if node:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                res.append('None')
        return '[' + ','.join(res) + ']'

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return []
        dataList = data[1:-1].split(',')
        root = TreeNode(int(dataList[0]))
        queue = collections.deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if dataList[i] != 'None':
                node.left = TreeNode(int(dataList[i]))
                queue.append(node.left)
            i += 1
            if dataList[i] != 'None':
                node.right = TreeNode(int(dataList[i]))
                queue.append(node.right)
            i += 1
        return root

Myleswork commented 2 years ago

思路

今天这题明天再看看，这题两个函数是联动的，先序列化再逆序列化，不是单个自己调用的，所以在处理空节点的时候需要先标记。

序列化就是通过借助队列这一数据结构，节点进队列，出队列时让其左右子节点进队列，直到队列为空，说明已经遍历所有节点。

代码

/**
 * 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) {
        string res;
        if (!root) return res;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            while (len--) {
                TreeNode* node = q.front();
                if (node) {
                    res += to_string(node->val) + ',';
                    q.push(node->left);
                    q.push(node->right);
                } else {
                    res += "#,";
                }
                q.pop();
            }
        }
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()) return NULL;
        vector<string> dataArr;
        split(dataArr, data, ',');
        int i = 0;
        TreeNode* root = new TreeNode(stoi(dataArr[i++]));
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int len = q.size();
            while (len--) {
                TreeNode* node = q.front();
                q.pop();

                string leftVal = dataArr[i++];
                string rightVal = dataArr[i++];
                if (leftVal != "#") {
                    node->left = new TreeNode(stoi(leftVal));
                    q.push(node->left);
                }
                if (rightVal != "#") {
                    node->right = new TreeNode(stoi(rightVal));
                    q.push(node->right);
                }
            }
        }
        return root;
    }
    void split(vector<string>& list, const string& s, const char delimiter) {
        list.reserve(s.size());
        size_t start;
        size_t end = 0;
        while ((start = s.find_first_not_of(delimiter, end)) != string::npos) {
            end = s.find(delimiter, start);
            list.push_back(s.substr(start, end - start));
        }
        list.shrink_to_fit();
    }
};

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

复杂度分析

时间复杂度：O(n) n为节点个数

空间复杂度：O(h) h为二叉树的深度（有待考究）

z1ggy-o commented 2 years ago

思路

首先是想到可以用 array 来对树进行表达。然后把 array 变成 string 就很简单了。但是试了一下发现，如果树比较的稀疏，用最基本的表达方式会浪费许多的空间。

参考了题解发现，可以在 deserialized 的时候通过递增 array index 而不是原本的计算的方式来获取 child nodes。

具体的来讲说，原来的表达方式为：

假设 parent node 在 array 中的 index 为 n
则 left child 的 index 为 2n
right child 的 index 为 2n+1

直接使用这样的表达方式，就算对应的位置实际上没有 node，也要为其预留 slot。因为上面的计算关系是根据完全树来说的。为了避免这样的空间浪费，我们实际上可以只为 leaf node 为止的 node 记录，然后相应的更新 index（idx = idx + 2）。index 如此更新的理由和完全树是一样的，但是当面对最后一层 leaf node 的时候，我们没有记录其 children，相应的也不更新 index.

2*n == 2 相加 n 次。

代码

CPP

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        // bfs
        queue<TreeNode *> q;
        string str = "";

        q.push(root);
        while (!q.empty()) {
            auto node = q.front();
            q.pop();
            if (node) {
                str += to_string(node->val) + ",";
                q.push(node->left);
                q.push(node->right);
            } else {
                str += "#,";
            }
        }
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        vector<string> results;
        TreeNode *root, *left, *right;
        queue<TreeNode *> q;
        int idx;

        if (data == "#,") return nullptr;

        stringstream  ss(data);
        string s;
        while (getline(ss, s, ',')) {
            results.push_back(s);
        }

        root = new TreeNode(stoi(results[0]));
        q.push(root);
        idx = 1;
        while (!q.empty()) {
            auto node = q.front();
            q.pop();

            auto lv = results[idx];
            auto rv = results[idx+1];

            if (lv.compare("#")) {  // compare() return 0 when equal
                left = new TreeNode(stoi(lv));
                node->left = left;
                q.push(left);
                cout << "linked left" << endl;
            }
            if (rv.compare("#")) {
                right = new TreeNode(stoi(rv));
                node->right = right;
                q.push(right);
                cout << "linked right" << endl;
            }

            idx += 2;
        }
        return root;
    }
};

复杂度分析

时间：O(n)，遍历了所有的 nodes
空间：O(n), queue 的最大长度可以达到 n/2

simbafl commented 2 years ago

from collections import deque
class Codec:
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if not root: return []
        q = deque()
        q.append(root)
        res = ''
        while q:
            node = q.popleft()
            if node != None:
                res += str(node.val) + ','
                q.append(node.left)
                q.append(node.right)
            else:
                res += 'X,'
        return res

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

        :type data: str
        :rtype: TreeNode
        """
        if not data: return None
        data = data.split(',')
        root = TreeNode(data.pop(0))
        q = [root]
        while q:
            node = q.pop(0)
            if data:
                val = data.pop(0)
                if val != 'X':
                    node.left = TreeNode(val)
                    q.append(node.left)
            if data:
                val = data.pop(0)
                if val != 'X':
                    node.right = TreeNode(val)
                    q.append(node.right)
        return root

xjhcassy commented 2 years ago

class Codec:
    def serialize(self, root):
        ans = ''
        queue = [root]
        while queue:
            node = queue.pop(0)
            if node:
                ans += str(node.val) + ','
                queue.append(node.left)
                queue.append(node.right)
            else:
                ans += '#,'
        print(ans[:-1])
        return ans[:-1]

    def deserialize(self, data: str):
        if data == '#': return None
        nodes = data.split(',')
        if not nodes: return None
        root = TreeNode(nodes[0])
        queue = [root]
        # 已经有 root 了，因此从 1 开始
        i = 1

        while i < len(nodes) - 1:
            node = queue.pop(0)
            lv = nodes[i]
            rv = nodes[i + 1]
            i += 2
            if lv != '#':
                l = TreeNode(lv)
                node.left = l
                queue.append(l)

            if rv != '#':
                r = TreeNode(rv)
                node.right = r
                queue.append(r)
        return root

babyyre commented 2 years ago

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);
    StringBuilder sb = new StringBuilder();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        sb.append(node != null ? node.val : "null");
        if (node != null) {
            queue.offer(node.left);
        }
        if (node != null) {
            queue.offer(node.right);
        }
        if (!queue.isEmpty()) {
            sb.append(",");
        }
    }
    return sb.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
    if (data == null || data.length() == 0) return null;
    String[] datas = data.split(",");
    LinkedList<String> list = new LinkedList<>(Arrays.asList(datas));
    Queue<TreeNode> queue = new LinkedList<>();
    TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
    queue.offer(root);
    list.remove(0);
    while (!queue.isEmpty()) {
         TreeNode node = queue.poll();
         String arg = list.get(0);
         list.remove(0);
         if (!"null".equals(arg)) {
             node.left = new TreeNode(Integer.valueOf(arg));
             queue.offer(node.left);
         } 

         arg = list.get(0);
         list.remove(0);
         if (!"null".equals(arg)) {
             node.right = new TreeNode(Integer.valueOf(arg));
             queue.offer(node.right);
         } 

    }
    return root;
}

}

last-Battle commented 2 years ago

代码

语言支持：C++

C++ Code:


class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

    void serialize(TreeNode *root, ostringstream &out) {
        if (root != nullptr) {
            out << root->val << ' ';
            serialize(root->left, out);
            serialize(root->right, out);
        } else {
            out << "# ";
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream in(data);
        return deserialize(in);
    }

    TreeNode* deserialize(istringstream &in) {
        string val;
        in >> val;
        if (val == "#") {
            return nullptr;
        }

        TreeNode *root = new TreeNode(stoi(val));
        root->left = deserialize(in);
        root->right = deserialize(in);

        return root;
    }
};

复杂度分析

时间复杂度：$O(n)$
空间复杂度：$O(n)$

moirobinzhang commented 2 years ago

思路：树的遍历，可以采用DFS或者BFS解决

代码： public class Codec {

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

    string result = root.val.ToString() + "!";
    result += serialize(root.left);
    result += serialize(root.right);
    return result;       
}

// Decodes your encoded data to tree.
public TreeNode deserialize(string data) {

    string[] nodeValues = data.Split("!");
    Queue<string> nodeQueue = new Queue<string>();
    for (int i = 0 ; i < nodeValues.Length; i++ )
        nodeQueue.Enqueue(nodeValues[i]);

    return deserializeHelper(nodeQueue);        
}

public TreeNode deserializeHelper(Queue<string> nodeQueue)
{
    if (nodeQueue.Count == 0)
        return null;

    string currentVal = nodeQueue.Dequeue();
    if (currentVal == "#")
        return null;

    TreeNode currentRoot = new TreeNode(Convert.ToInt32(currentVal));
    currentRoot.left = deserializeHelper(nodeQueue);
    currentRoot.right = deserializeHelper(nodeQueue);

    return currentRoot;
}

}

Aobasyp commented 2 years ago

思路 DFS ,使用前序遍历

class Codec: def serialize(self, root): def preorder(root): if not root: return "null," return str(root.val) + "," + preorder(root.left) + preorder(root.right)

    return preorder(root)[:-1]

def deserialize(self, data: str):
    nodes = data.split(",")

    def preorder(i):
        if i >= len(nodes) or nodes[i] == "null":
            return i, None
        root = TreeNode(nodes[i])
        j, root.left = preorder(i + 1)
        k, root.right = preorder(j + 1)
        return k, root

    return preorder(0)[1]

时间复杂度：O(N) 空间复杂度：O(h)

alongchong commented 2 years ago

思路

代码

public class Codec {
    String str = "";

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

            str += root.val + ",";
            serialize(root.left);
            serialize(root.right);

        }
        return str;
    }

    // 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 rdeserialize(dataList);
    }

 public TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals("None")) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.valueOf(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
        }
    }

复杂度分析 时间复杂度：$0(N)$ 空间复杂度：$0(N)$

uniqlell commented 2 years ago

public class Codec {

public String serialize(TreeNode root) {      //用StringBuilder
    StringBuilder res = ser_help(root, new StringBuilder());
    return res.toString();
}

public StringBuilder ser_help(TreeNode root, StringBuilder str){
    if(null == root){
        str.append("null,");
        return str;
    }
    str.append(root.val); 
    str.append(",");
    str = ser_help(root.left, str);
    str = ser_help(root.right, str);
    return str;
}

public TreeNode deserialize(String data) {
    String[] str_word = data.split(",");
    List<String> list_word = new LinkedList<String>(Arrays.asList(str_word));
    return deser_help(list_word);
}

public TreeNode deser_help(List<String> li){
    if(li.get(0).equals("null")){
        li.remove(0);
        return null;
    }
    TreeNode res = new TreeNode(Integer.valueOf(li.get(0)));
    li.remove(0);
    res.left = deser_help(li);
    res.right = deser_help(li);
    return res;
}

}

naomiwufzz commented 2 years ago

思路：dfs

有两个地方需要注意：

（1）node节点可能是负数的，所以还需要分割符号的

（2）反序列化自己做的时候node建好之后拼左右节点的时候有点拼迷茫了。有点不清楚输入的序列应该是d[1:]还是碰到#？看了别人的觉得很神奇，只要传d就足够了，因为d是动态的，d一直在pop，左边拼完拼右边的时候左边已经遍历完了其实。

代码

# 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 __init__(self):
        self.res = ""
    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        self.res = ""
        def dfs(node):
            if not node:
                self.res += ",#"
                return
            self.res += ","+str(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return self.res[1:]

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

        :type data: str
        :rtype: TreeNode
        """
        data = data.split(",")
        def dfs(d):
            if not d:
                return None
            cur_node = d.pop(0)
            if cur_node == "#":
                return None
            else:

                cur_node = TreeNode(int(cur_node))
                cur_node.left = dfs(d)
                cur_node.right = dfs(d)
            return cur_node
        res = dfs(data)
        print(res)
        return res

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

复杂度分析

时间复杂度：O(n)
空间复杂度：O(h)

思路：bfs

序列化是好想的。反序列化比较难想的地方是如果左边整块是空的那么下一个节点拼到哪里？这时候还是用队列，把合法的节点全部放到队列中，一个个出队，每个出队的节点左右节点拼序列化的下一个节点和下下个节点，并且左右节点进队

代码

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

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

        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return ""
        res = ""
        queue = deque([root])
        while queue:
            for _ in range(len(queue)):
                cur_node = queue.popleft()
                if cur_node:
                    res += "," + str(cur_node.val)
                    queue.append(cur_node.left)
                    queue.append(cur_node.right)
                else:
                    res += ",#"
        print(res)
        return res[1:]

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

        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        data = data.split(',')

        root = TreeNode(int(data.pop(0)))
        queue = deque([root])
        while queue:
            cur_node = queue.popleft()
            left = data.pop(0)
            right = data.pop(0)
            if left != "#":
                cur_node.left = TreeNode(int(left))
                queue.append(cur_node.left)
            if right != "#":
                cur_node.right = TreeNode(int(right))
                queue.append(cur_node.right)
        return root

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

复杂度分析

时间复杂度：O(n)
空间复杂度：O(w)

linyang4 commented 2 years ago

思路

DFS

代码

var serialize = function(root) {
    const res = []
    const getTreeNode = (node) => {
        if (node === null) {
            res.push('n')
            return
        }
        res.push(node.val)
        getTreeNode(node.left)
        getTreeNode(node.right)
    }
    getTreeNode(root)
    return res.join(',')
}

var deserialize = function(data) {
    data = data.split(',')
    const buildTree = (list) => {
        if (list[0] ==='n') {
            list.shift()
            return null
        }
        const node = new TreeNode(list[0])
        list.shift()
        node.left = buildTree(list)
        node.right = buildTree(list)
        return node
    }
    return buildTree(data)
}

复杂度

时间复杂度: O(n)
空间复杂度: O(n)

15691894985 commented 2 years ago

day17 297. 二叉树的序列化与反序列化

https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

BFS:

按完全二叉树形式进行序列化，去除多余的空节点
反序列化的时候，给二叉树编码，因为根节点对应两个子节点，用p1,p2,p2分别表示数据中第一个根节点，根节点对应的左节点，根节点对应的右节点，每遍历到一个根节点到到下一个是是按

p1移动一位，p2和p3移动两位走

代码：

# 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):
        q1 = collections.deque([root])
        ans = ''
        while q1:
            cur = q1.popleft()
            if cur:
                ans += str(cur.val)+','
                q1.append(cur.left)
                q1.append(cur.right)
            else:
                ans += 'null,'
        return ans[:-1]

    def deserialize(self, data):
        if data == 'null':
            return None
        nodes = data.split(',')
        if not nodes: return None
        root = TreeNode(nodes[0])
        q = collections.deque([root])
        i = 1
        while q and i < len(nodes)-1:
            cur = q.popleft()  #取出下一个点
            left = nodes[i]
            right = nodes[i+1]
            i +=2
            if left !='null':
                l = TreeNode(left)
                q.append(l)
                cur.left = l
            if right !='null':
                r = TreeNode(right)
                q.append(r)
                cur.right = r
        return root

复杂度分析：

时间复杂度：O(N),N为树的节点
空间复杂度：O(q) q为队列，最坏情况满二叉树 N

guangsizhongbin commented 2 years ago

/**

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) { // 遍历到null节点 if (root == null){ return "null"; }
```
return root.val + "," + serialize(root.left) + "," + serialize(root.right); 
```
}

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

private TreeNode dfs(Queue queue) { String val = queue.poll(); if ("null".equals(val)){ return null; } TreeNode root = new TreeNode(Integer.parseInt(val)); root.left = dfs(queue); root.right = dfs(queue); 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));

biscuit279 commented 2 years ago

思路:

dfs ···

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
    """
    def preorder(root):
        if not root:
            return 'null,'
        return (str(root.val) + ',' + preorder(root.left) + preorder(root.right))
    ans = preorder(root)
    return ans[0:-1] 

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

    :type data: str
    :rtype: TreeNode
    """
    nodes = data.split(',')
    def preorder(i):
        if i >= len(nodes) or nodes[i] == 'null':
            return i, None
        root = TreeNode(nodes[i])
        j,root.left = preorder(i+1)
        k,root.right = preorder(j+1)
        return k,root
    return preorder(0)[1]

Your Codec object will be instantiated and called as such:

ser = Codec()

deser = Codec()

ans = deser.deserialize(ser.serialize(root))

··· 时间复杂度：O（n）空间复杂度：O（h）

L-SUI commented 2 years ago

var serialize = function(root) {
    return rserialize(root, '');
};

var deserialize = function(data) {
    const dataArray = data.split(",");
    return rdeserialize(dataArray);
};

const rserialize = (root, str) => {
    if (root === null) {
        str += "None,";
    } else {
        str += root.val + '' + ",";
        str = rserialize(root.left, str);
        str = rserialize(root.right, str);
    }
    return str;
}

const rdeserialize = (dataList) => {
    if (dataList[0] === "None") {
        dataList.shift();
        return null;
    }

    const root = new TreeNode(parseInt(dataList[0]));
    dataList.shift();
    root.left = rdeserialize(dataList);
    root.right = rdeserialize(dataList);

    return root;
}

Previous Next