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

/**
 * 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:

    string itoa(long i)
    {
        char buff[100];
        sprintf(buff, "%lld", i);
        return buff;
    }
   
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string ret = "";

        if (root == 0)
            return ret;
       
        stack<TreeNode*> tmp;
        tmp.push(root);
       
        while (!tmp.empty())
        {
            TreeNode* node = tmp.top();
            tmp.pop();
            string idstr = itoa((long)node);
            string data = itoa(node->val);
            string left = itoa((long)node->left);
            string right = itoa((long)node->right);
            string str = idstr + "," + data + "," + left + ","+ right + "|";
            ret += str;
            if (node->left != 0)
            {
                tmp.push(node->left);
            }
            if (node->right != 0)
            {
                tmp.push(node->right);
            }
        }

        return ret;
    }

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

        map<int, TreeNode*> tmp;
        TreeNode* root = 0;
        string str;
        while (true)
        {
            int index = data.find_first_of("|");
            if (index == -1)
            {
                break;
            }

            str = data.substr(0, index);
            data = data.substr(index+1);
            char * p = strtok((char *)str.c_str(), ",");
            long id = atol(p);
            p = strtok(0, ",");
            long val = atol(p);
            p = strtok(0, ",");
            long left = atol(p);
            p = strtok(0, ",");
            long right = atol(p);

            TreeNode * cur = tmp[id];
            if (cur == 0)
            {
                cur = new TreeNode(0);
                tmp[id] = cur;
                if (root == 0)
                {
                    root = cur;
                }
            }
            if (tmp[left] == 0)
            {
                tmp[left] = new TreeNode(0);
            }
            if (tmp[right] == 0)
            {
                tmp[right] = new TreeNode(0);
            }
            cur->val = val;
            cur->left = left != 0?tmp[left]:0;
            cur->right = right != 0?tmp[right]:0;
        }
        return root;
    }
};

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