序列化、反序列化二叉树

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数： | 阅读次数：

LeetCode 297. Serialize and Deserialize Binary Tree

实现一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Codec {
public:

    string serialize(TreeNode* root) {
        ostringstream out;
        serialize(root, out);
        return out.str();
    }

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

deserialize 实现二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode* deserialize(istringstream& in) {
      int n;
      char ch;
      in >> n;   //从前序遍历顺序的 序列化二叉树中读取一个字符，转化为int。（>>运算符遇空白符e.g.空格、制表符、换行中止）
      if(in.fail()) {   //当读取失败时，in的fail() 返回 true。 (注1)

          in.clear();   // 调用流对象的clear()， 复位流的所有条件状态。
          in >> ch;    // 用一个char字符读取流中的下一位字符（即#）。
          return nullptr;
      }
          
      
      TreeNode* root = new TreeNode(n);
      root->left = deserialize(in);
      root->right = deserialize(in);
      return root;
  }

注1： 

1
2
int val;
cin >> val;

如果我们输入Boo, 上面的读操作就会失败。代码中的输入运算符期待读取一个int, 但却得到了一个字符B。这样，cin 会进入错误状态（类似的，如果输入一个eof，cin也会进入错误状态）。一个流一旦发生错误，其上后续的IO操作都会失败。只有当一个流处于无错状态时，我们才可以从它读取数据，向它写入数据。由于流可能处于错误状态，因此代码通常应该在使用一个流之前检查它是否处于良好状态。
确定一个流对象的状态的最简单的方法是将它当作一个条件来使用 ：

1
while (cin >> n) // while 循环检查 >> 表达式返回的流的状态。如果输入操作成功，流保持有效状态， 则条件为真

上述deserialize代码还可改为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

TreeNode* deserialize(istringstream& in) {
     int n;
     char ch;
        
     if(!(in >> n)) {   
         in.clear();  
         in >> ch;  
         return nullptr;
     }
         
     
     TreeNode* root = new TreeNode(n);
     root->left = deserialize(in);
     root->right = deserialize(in);
     return root;
 }

总之就是记住 流一旦发生错误，其后续IO操作都会失败，所以下次IO操作前要先用clear()清空（或者叫复位）条件状态标志位。

stoi()

将string 转化为int 所谓stoi 是不是 string to int …
虽然在上面哪个题里 stringstream 也可以进行数据类型转换， 但是 从输入流里往 int类型对象里读入（存入）数据 遇到 # 就会中断。

0%