Re: [閒聊] 每日leetcode

[sixB (6B)]

297. serialize and deserialize binary tree

grind75題隨便寫

用preorder放 然後再拿出來

原本在想要區分nullptr所以分了4種case

其實空格切一切 擺個符號就好了==

看solution原來 stringstream 能用

印象中開這個會跑很慢？

/**
 * 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.
    string serialize(TreeNode* root) {
        if(root == nullptr) return "";
        if(root->left == nullptr){
            if(root->right == nullptr){
                //type a :00
                cout << root->val << ";a, ";
                return to_string(root->val) + ";a,";
            }
            else{
                //type b:01
                cout << root->val  << ";b, ";
                return to_string(root->val) + ";b," + serialize(root->right);
            }
        }
        if(root->right == nullptr){
            //type c:10
            cout << root->val  << ";c, ";
            return to_string(root->val) + ";c," + serialize(root->left);
        }
        else {
            // type d:11
            cout << root->val  << ";d, ";
            return to_string(root->val) + ";d," + serialize(root->left) + serialize(root->right);
        }
    }

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

        if(data == "") return nullptr;
        cout << endl << data << endl;
        //char delimiter_val = ";"  char delimiter_type = ","

        queue<int> vals;
        queue<char> types;
        std::string::size_type begin, end;
        end = data.find(";");
        begin = 0;
        while(end != std::string::npos){
            if (end - begin != 0) {
                vals.push( stoi( data.substr( begin, end - begin)));
            }
            begin = end + 1;
            end = data.find(",", begin);
            if (end - begin != 0){
                types.push( data.substr( begin, end - begin)[0]);
            }
            begin = end + 1;
            end = data.find(";", begin);
        }


        TreeNode* mutsumi = new TreeNode();
        Build_A_Small_Tree(vals, types, mutsumi);
        return mutsumi;
    }
    TreeNode* Build_A_Small_Tree(queue<int>& vals, queue<char>& types, TreeNode* root){
        if(vals.empty()) return root;

        root->val = vals.front();
        vals.pop();
        char t = types.front();
        types.pop();

        if(t=='b'){
            root->right = Build_A_Small_Tree(vals, types, new TreeNode());
        }
        else if(t=='c'){
            root->left = Build_A_Small_Tree(vals, types, new TreeNode());
        }
        else if(t=='d'){
            root->left = Build_A_Small_Tree(vals, types, new TreeNode());
            root->right = Build_A_Small_Tree(vals, types, new TreeNode());
        }

        return root;
    }

};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));
-----
Sent from JPTT on my iPad

--
很姆的咪

姆之咪

http://i.imgur.com/5sw7QOj.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.205.121.194 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715901941.A.2A5.html
※ 編輯: sixB (123.205.121.194 臺灣), 05/17/2024 07:26:19
推 SecondRun: 大師