Ex37 序列化二叉树

题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

解题思路

利用中序遍历就好。

代码

/**
 * 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.
  std::string
  serialize (TreeNode *root)
  {
    std::string str ("");
    serialize_core (root, str);
    return str;
  }

  // Decodes your encoded data to tree.
  TreeNode *
  deserialize (std::string data)
  {
    int begin = 0;
    return deserialize_core (data, &begin);
  }

private:
  void
  serialize_core (TreeNode *root, std::string &str)
  {
    if (!root)
      {
        str.append ("null|");
        return;
      }
    str.append (std::to_string (root->val));
    str.append ("|");
    serialize_core (root->left, str);
    serialize_core (root->right, str);
  }

  TreeNode *
  deserialize_core (std::string &data, int *index)
  {
    int space_index = data.find ("|", *index);
    if (space_index == -1)
      return nullptr;
    std::string tmp (data, *index, space_index - *index);
    *index = space_index + 1;
    if (tmp == "null")
      {
        return nullptr;
      }
    TreeNode *root = new TreeNode (std::stoi (tmp));
    root->left = deserialize_core (data, index);
    root->right = deserialize_core (data, index);
    return root;
  }
};

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

结果

执行结果：通过

执行用时：64 ms, 在所有 C++ 提交中击败了73.45%的用户

内存消耗：32.5 MB, 在所有 C++ 提交中击败了30.14%的用户