面试题37. 序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。
示例:
你可以将以下二叉树：

     1
   /    \
  2     3 
      /    \
     4      5

序列化为 "[1,2,3,null,null,4,5]"

思路：

使用层序遍历，序列化二叉树，结点为空时不进入队列，不论结点是否为空字符串都应添加该结点。
反序列二叉树，应先将字符串分割为字符向量，向量中每个元素，代表每个结点，再重构二叉树

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        if (!root)
            return s;
        queue<TreeNode *> q;
        q.push(root);
        s += to_string(root->val) + ","; //将数值转换为字符串
        while (!q.empty())
        {
            TreeNode *tmp = q.front();  //取出队列首元素
            if (tmp->left)       //空不进队列
            {
                s += to_string(tmp->left->val) + ",";
                q.push(tmp->left);
            }
            else  //为空时不进队列，但是字符串要添加
                s += "null,";
            if (tmp->right)  //空不进队列
            {
                s += to_string(tmp->right->val) + ",";
                q.push(tmp->right);
            }
            else
                s += "null,";
            q.pop(); //弹出队列首元素
        }
        return s;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string s) {
        if(s.size()==0)
            return NULL;
        vector<string> data = splitString(s); 将一整个字符串分割为 字符串向量
        int itmp = stoi(data[0]);  //将数字字符串转换为 int
        TreeNode *head = new TreeNode(itmp);
        TreeNode *phead = head;
        queue<TreeNode *> q;
        q.push(head);
        for (int i = 1; i<data.size(); )
        {
            TreeNode *tmp = q.front(); //考察tmp结点的左右孩子
            if (data[i] != "null")   //不为空时入队，并构建左孩子
            {
                itmp = stoi(data[i++]);   //i+1，i指向右孩子
                tmp->left = new TreeNode(itmp);
                q.push(tmp->left);
            }
            else
                ++i;
            if (data[i] != "null")   //不为空时入队，并构建右孩子
            {
                itmp = stoi(data[i++]);
                tmp->right = new TreeNode(itmp);
                q.push(tmp->right);
            }
            else
                ++i;
            q.pop(); //弹出已构建完成的结点
        }
        return phead;
    }
    vector<string> splitString(string s) //以 ',' 分割字符串为字符串向量
    {
        vector<string> v;
        int i = 0, j = 1;
        for (; i<s.size();)
        {
            while (s[j] != ',') //不等于 ',' 时 j++，最终 j 位置为 ','
            {
                ++j;
            }
            v.push_back(s.substr(i, j - i)); 获取子串
            i = j + 1; //i更新为j的下一个位置
            j = i + 1; //j更新为新i的下一个位置
        }
        return v;
    }
};

小知识

1. 将数值转换为字符串
   string to_string(val)，将数值转换为字符串，并返回相应的字符串。
2. 将数字字符串转换为int
   string s("123")
stoi(s) 当s超出int范围时会报错，runtime error；
   atoi(s.c_str()) 超出int上界时输出上界，超出int下界时输出下界，需要将string类型转换为char *。
3. 子字符串
   s.substr(pos, n)
   截取从pos位置开始，n个元素，并返回截取的字符串，pos的默认值是0，n的默认值是s.size() - pos，即不加参数会默认拷贝整个s）
   若pos的值超过了string的大小，则substr函数会抛出一个out_of_range异常；若pos+n的值超过了string的大小，则substr会调整n的值，只拷贝到string的末尾。