449.序列化和反序列化二叉搜索树

两天宇宙人

2020-01-17

递归实现

先序遍历，类似于数组表示二叉树

class Codec {
public:
    void se_helper(TreeNode* root, string& str) {
        if(!root) { 
            str += "x#";
            return ;
        }
        str += to_string(root->val) + '#';
        se_helper(root->left, str);
        se_helper(root->right, str);
    }

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

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "x#")
            return nullptr;
        auto iter = data.begin();
        return deserialize1(iter, data.end());
    }

    TreeNode* deserialize1(string::iterator& iter, string::iterator end) 
    {
        if(iter == end) 
            return nullptr;
        string s;
        while(*iter != '#') {
            s += *iter++;
        }    
        ++iter;
        if(s == "x") 
            return nullptr;
        int val = atoi(s.c_str());
        TreeNode* newOne = new TreeNode(val);
        newOne->left = deserialize1(iter, end);
        newOne->right = deserialize1(iter, end);
        return newOne;
    }
};