【Day 17 】2024-04-24 - 297. 二叉树的序列化与反序列化

[azl397985856]

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 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

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

[xil324]

/**

• Encodes a tree to a single string.
• @param {TreeNode} root

• @return {string} */ var serialize = function(root) { const serializationRes = []; traverseToSerializeTree(root, serializationRes); return serializationRes.join(';');

  function traverseToSerializeTree(node, result) { if(!node) { result.push('NULL'); return; } result.push(node.val); traverseToSerializeTree(node.left, result); traverseToSerializeTree(node.right, result); } };

/**

• Decodes your encoded data to tree.
• @param {string} data

• @return {TreeNode} */ var deserialize = function(data) { if(!data) return []; const nodeList = data.split(';'); return traverseToGenerateTree(nodeList);

  function traverseToGenerateTree(nodes) { const value = nodes.shift(); if(value === 'NULL' || !nodes.length) return null; const node = new TreeNode(value) node.left = traverseToGenerateTree(nodes); node.right = traverseToGenerateTree(nodes); return node; }

};

[sanjiu81]

思路：先序遍历 代码： 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;

} 时间空间复杂度均为O(n)

[CathyShang]

思路：

• 先序遍历，没有叶子节点为“None”
• 反序列化，字符串根据逗号列表<字符串>
  • 从左到右，先序遍历
  • 同时，擦去遍历过的元素，List.erase(List.begin()); 其中，List.begin()为列表第一个元素的迭代器

难点数据结构转换，序列化与反序列化需要数据结构转换

代码：

class Codec {
public:
    void preOrder(TreeNode* root, string& str){
        if(root==nullptr){
            str += "None,";
        }
        else{
        str += to_string(root->val) + ",";
        preOrder(root->left, str);
        preOrder(root->right,str);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        preOrder(root, str);
        cout << str << endl;
        return str;
    }

    // Decodes your encoded data to tree.
    TreeNode* rdserialize(list<string>& dataArray){
        if(dataArray.front()=="None"){
            dataArray.erase(dataArray.begin());
            return nullptr;
        }
        TreeNode* root = new TreeNode(stoi(dataArray.front()));
        dataArray.erase(dataArray.begin());
        root->left = rdserialize(dataArray);
        root->right = rdserialize(dataArray);
        return root;
    }

    TreeNode* deserialize(string data) {
        list<string> dataArray;
        string str;
        for(auto& ch: data){
            if(ch==','){
                dataArray.push_back(str);
                // cout << str << ", ";
                str.clear();
            }else{
                str.push_back(ch); // 字符变字符串
            }
        }
        // the lastest one
        if(!str.empty()){
            dataArray.push_back(str);
            // cout << str << ", ";
            str.clear();
        }
        // cout << endl;
        // 字符串 变 字符串列表
        return rdserialize(dataArray);

    }
};

复杂度：

• 时间 $O(N)$ 需要遍历每一个节点
• 空间 $O(N)$

[hillsonziqiu]

思路

深度优先遍历。 序列化：如果tree为空，则直接拼接字符串 'None,'. 否则字符串拼接当前节点的value，并分别执行左侧节点和右侧节点的方法。最终返回拼接到的字符串。 反序列化：判断第一个拿出的值是否是none，如果是，则为空。否则就从头部获取值，并创建node节点。再通过递归获取左侧的节点和右侧的节点。

代码

/*
 * @lc app=leetcode.cn id=297 lang=javascript
 *
 * [297] 二叉树的序列化与反序列化
 */

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

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

    return str;
}

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function(root) {
    return reSerialize(root, '');
};

const reDeserialize = (data) => {
  if (data[0] === 'None') {
    data.shift();
    return null;
  }

  let root = new TreeNode(data[0]);
  data.shift();
  root.left = reDeserialize(data);
  root.right = reDeserialize(data);

  return root;
}

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

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
// @lc code=end

复杂度分析

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

[GReyQT]

/**

• 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 == nullptr) { return res.append("#"); // 如果根节点为空，直接返回， }

  queue<TreeNode*> q;
  q.push(root); // 将根节点入队
  while (!q.empty()) 
  {
      TreeNode* current = q.front(); // 获取队列头部节点
      res.append(to_string(current->val));
  
      q.pop(); // 将头部节点出队
  
      // 如果有左子节点，将左子节点入队
      if (current->left != nullptr) 
      {
          q.push(current->left);
      }
      else
      {
          res.append("#"); 
      }
      // 如果有右子节点，将右子节点入队
      if (current->right != nullptr) 
      {
          q.push(current->right);
      }
      else
      {
          res.append("#"); 
      }
  }
  
  cout<<res<<endl;
  
  return res;

  }

  // Decodes your encoded data to tree. TreeNode* deserialize(string data) { if( data[0] == '#') { return nullptr; }

  TreeNode* root = new TreeNode(data[0] - '0');
  
  size_t i = 1;
  
  queue<TreeNode*> q;
  q.push(root); // 将根节点入队
  
  while (!q.empty() && i < data.size()) 
  {
      TreeNode* current = q.front(); // 获取队列头部节点
      q.pop(); // 将头部节点出队
  
      //创建左节点
      if (i < data.size() && data[i] != '#') 
      {
          current->left = new TreeNode(data[i] - '0');
          q.push(current->left);
      }
      else if (i < data.size() && data[i] == '#') 
      {
          current->left = nullptr;
      }
      i++;
  
      //创建右节点
      if (i < data.size() && data[i] != '#') 
      {
          current->left = new TreeNode(data[i] - '0');
          q.push(current->right);
      }
      else if (i < data.size() && data[i] == '#') 
      {
          current->right = nullptr;
      }
      i++;
  }
  
  return root;

  } };

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

[Dtjk]

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;
    }
}

[smallppgirl]

class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        res = ""
        if not root:
            return res
        q = collections.deque()
        q.append(root)
        while q:
            node = q.popleft()
            if node:
                res = res + str(node.val) + ","
                q.append(node.left)
                q.append(node.right)
            else:
                res = res + "null,"
        return res.rstrip(",")

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

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

[zhiyuanpeng]

from collections import deque
class Codec:

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

        :type root: TreeNode
        :rtype: str
        """
        nodes = []
        self. encode_dfs(root, nodes)
        return ",".join(nodes)

    def encode_dfs(self, root, nodes):
        if not root:
            nodes.append("null")
            return
        nodes.append(str(root.val))
        self.encode_dfs(root.left, nodes)
        self.encode_dfs(root.right, nodes)

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

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

    def decode_dfs(self, data):
        if not data:
            return None
        val = data.popleft()
        if val == "null":
            return None
        node = TreeNode(val)
        node.left = self.decode_dfs(data)
        node.right = self.decode_dfs(data)
        return node

time O(N) space O(N)

[YANGLimbo]

//#include <queue>
class Codec {
public:

    // use BFS level-order traverse 使用队列的层序遍历（属于bfs）

    // 写了一堆发现没有办法处理"null"转化为int的情况，这里试试看能不能用C++17的std::nullopt来表示，勉强解决一下。。
    string intVectorToString(vector<std::optional<int>>& v){
        string s;
        for(int i = 0; i<v.size();i++){
            if(v.at(i).has_value()){
                s+= to_string(v.at(i).value());
            }else{
                s+= "null";
            }
            if(i!=v.size()-1){
                s+=",";
            } 
        }
        //cout << "string is " << s << endl;
        return s;
    }

    vector<std::optional<int>> stringToIntVector(string s){
        size_t start = 0, pos = 0;
        vector<std::optional<int>> v;
        do{
            pos = s.find(",",start);
            if(pos == string::npos){
                // 找不到splitter了
                pos = s.length();
            }
            string token = s.substr(start, pos-start);
            if(token == "null"){
                v.push_back(std::nullopt);
            }else{
                v.push_back(stoi(token));
            }
            start = pos+1;
        }while(pos < s.length());
        /*
            C++查找子字符串:
            size_t find(const std::string& str, size_t pos = 0) const;
            在调用者字符串中从索引 pos 开始搜索子字符串 str。
        */
        return v;
    }

// Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        if(root == nullptr){
            return "null";
        }
        vector<std::optional<int>> v;
        queue<TreeNode*> q;
        q.push(root);
        TreeNode* node; // current node
        while(!q.empty()){
            node = q.front();
            q.pop();
            if(node == nullptr){
                v.push_back(std::nullopt);
            }else{
                v.push_back(node->val);
                q.push(node->left);
                q.push(node->right);
            }
        }
        //Remove trailing None values to minimize data size
        // 因为有存在结尾好几个null的情况，可以考虑去除掉结尾倒数的连续的null，这样就符合leetcode的模式了~

        return intVectorToString(v);
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "null"){
            return nullptr;
        }
        vector<std::optional<int>> v = stringToIntVector(data);

        queue<TreeNode*> q;
        TreeNode* root = new TreeNode(v.at(0).value());
        q.push(root);
        TreeNode* node; // current node
        int i = 1;
        while(!q.empty() && i < v.size()){
            node = q.front();
            q.pop();
            if(v.at(i).has_value()){
                node->left = new TreeNode(v.at(i).value());
                q.push(node->left);
            }
            i++;
            if(v.at(i).has_value() && i < v.size()){ // 注意这里要小心过界
                node->right = new TreeNode(v.at(i).value());
                q.push(node->right);
            }
            i++;
        }
        return root;
    }
};

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