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

題意

• 給定一棵二叉搜索樹，實現(xiàn)序列化和反序列化；
• 注意 val 范圍，因此 在序列化時需要插入分隔符分割每個節(jié)點的 val；
• 要善于利用 二叉搜索樹的特性（中序遍歷 = 遞增排序）；

解法

• 前序遍歷 + 中序遍歷 可以重構(gòu)一棵樹，又由于二叉搜索樹自帶中序遍歷，因此在序列化時保存前序遍歷；
• 由于節(jié)點的 val 不一定是個位數(shù)，所以要在序列化時插入分隔符；
• 在反序列化時，首先分割字符串，得到前序遍歷，然后通過前序遍歷和中序遍歷進行二叉搜索樹的重構(gòu)。

/**
 * 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:
    void PreOrder(TreeNode* root, string& data)
    {
        if(root == nullptr) return;

        data.append(to_string(root->val) + ","); 	// , 作為分隔符

        // if(root->left != nullptr) 	遞歸函數(shù)開頭就判斷了非空的情況，因此這里不需要再次判斷了
        PreOrder(root->left, data);
        // if(root->right != nullptr) 	遞歸函數(shù)開頭就判斷了非空的情況，因此這里不需要再次判斷了
        PreOrder(root->right, data);
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res = "";

        PreOrder(root, res);

        return res;
    }

    vector<int> Split(string data) 	// 將序列化后的 string 進行分割，得到每個節(jié)點的 val
    {
        int idx = 0;
        int curS = 0;
        vector<int> ans;

        while(idx < data.size())
        {
            if(data[idx] == ',')
            {
                string cur = data.substr(curS, idx - curS);
                ans.emplace_back(stoi(cur));
                curS = idx + 1;
            }
            idx++;
        }
        return ans;
    }
    TreeNode* ReconstructTree(vector<int> data, int s, int t)
    {
        TreeNode* root = new TreeNode(data[s]);
        int rightIdx = -1;

        // 沒有孩子
        if(s == t)
            return root;

        // 尋找右孩子的根
        for(int i = s + 1; i <= t; i++)
        {
            if(data[i] > root->val)
            {
                rightIdx = i;
                break;
            }
        }

        if(rightIdx == -1)  // 沒有右孩子
        {
            root->right = nullptr;

            // 構(gòu)建左孩子
            root->left = ReconstructTree(data, s + 1, t);
        }
        else if(rightIdx == s + 1)  // 沒有左孩子
        {
            root->left = nullptr;
            // 構(gòu)建右孩子
            root->right = ReconstructTree(data, s + 1, t);
        }
        else
        {
            // 有左孩子，構(gòu)建左孩子和右孩子
            root->left = ReconstructTree(data, s + 1, rightIdx - 1);
            root->right = ReconstructTree(data, rightIdx, t);
        }

        return root;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if(data == "") return nullptr;

        vector<int> intData = Split(data);

        TreeNode* root = ReconstructTree(intData, 0, intData.size()-1);

        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;

復雜度

時間復雜度：O(N)，序列化前序遍歷每個節(jié)點，反序列化也是恢復每個節(jié)點；
空間復雜度：O(N)，存儲序列化后的字符串。文章來源地址http://www.zghlxwxcb.cn/news/detail-694969.html

到了這里，關于【LeetCode - 每日一題】449. 序列化和反序列化二叉搜索樹（23.09.04）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！