{"id":150093,"date":"2020-09-02T12:05:57","date_gmt":"2020-09-02T04:05:57","guid":{"rendered":"http:\/\/4563.org\/?p=150093"},"modified":"2020-09-02T12:05:57","modified_gmt":"2020-09-02T04:05:57","slug":"%e8%b0%b7%e6%ad%8c%e9%9d%a2%e8%af%95%e9%a2%98%ef%bc%9a%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e5%ba%8f%e5%88%97%e5%8c%96%e5%92%8c%e5%8f%8d%e5%ba%8f%e5%88%97%e5%8c%96","status":"publish","type":"post","link":"http:\/\/4563.org\/?p=150093","title":{"rendered":"\u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u4e8c\u53c9\u6811\u7684\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217\u5316"},"content":{"rendered":"
\n
\n
\n

\u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u4e8c\u53c9\u6811\u7684\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217\u5316 <\/h1>\n

<\/p>\n

\n
\u8cc7\u6df1\u5927\u4f6c : zzzrf <\/span> <\/i> 11<\/span> <\/div>\n
<\/div>\n<\/p><\/div>\n<\/p><\/div>\n<\/p><\/div>\n
<\/p>\n

\u8bbe\u8ba1\u4e00\u4e2a\u7b97\u6cd5\uff0c\u5e76\u7f16\u5199\u4ee3\u7801\u6765\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217\u5316\u4e8c\u53c9\u6811\u3002\u5c06\u6811\u5199\u5165\u4e00\u4e2a\u6587\u4ef6\u88ab\u79f0\u4e3a\u201c\u5e8f\u5217\u5316\u201d\uff0c\u8bfb\u53d6\u6587\u4ef6\u540e\u91cd\u5efa\u540c\u6837\u7684\u4e8c\u53c9\u6811\u88ab\u79f0\u4e3a\u201c\u53cd\u5e8f\u5217\u5316\u201d\u3002<\/p>\n

\u5982\u4f55\u53cd\u5e8f\u5217\u5316\u6216\u5e8f\u5217\u5316\u4e8c\u53c9\u6811\u662f\u6ca1\u6709\u9650\u5236\u7684\uff0c\u4f60\u53ea\u9700\u8981\u786e\u4fdd\u53ef\u4ee5\u5c06\u4e8c\u53c9\u6811\u5e8f\u5217\u5316\u4e3a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u5e76\u4e14\u53ef\u4ee5\u5c06\u5b57\u7b26\u4e32\u53cd\u5e8f\u5217\u5316\u4e3a\u539f\u6765\u7684\u6811\u7ed3\u6784\u3002<\/p>\n

\u5bf9\u4e8c\u8fdb\u5236\u6811\u8fdb\u884c\u53cd\u5e8f\u5217\u5316\u6216\u5e8f\u5217\u5316\u7684\u65b9\u5f0f\u6ca1\u6709\u9650\u5236\uff0cLintCode \u5c06\u60a8\u7684 serialize \u8f93\u51fa\u4f5c\u4e3a deserialize \u7684\u8f93\u5165\uff0c\u5b83\u4e0d\u4f1a\u68c0\u67e5\u5e8f\u5217\u5316\u7684\u7ed3\u679c\u3002<\/p>\n

\u70b9\u6b64\u5904\u5728\u7ebf\u505a\u9898<\/p>\n

\u6837\u4f8b 1\uff1a<\/h2>\n
\u8f93\u5165\uff1a{3,9,20,#,#,15,7} \u8f93\u51fa\uff1a{3,9,20,#,#,15,7} \u89e3\u91ca\uff1a \u4e8c\u53c9\u6811 {3,9,20,#,#,15,7}\uff0c\u8868\u793a\u5982\u4e0b\u7684\u6811\u7ed3\u6784\uff1a    3   \/   9  20    \/     15   7 \u5b83\u5c06\u88ab\u5e8f\u5217\u5316\u4e3a {3,9,20,#,#,15,7} <\/code><\/pre>\n
\u6837\u4f8b 2\uff1a<\/h2>\n
\u8f93\u5165\uff1a{1,2,3} \u8f93\u51fa\uff1a{1,2,3} \u89e3\u91ca\uff1a \u4e8c\u53c9\u6811 {1,2,3}\uff0c\u8868\u793a\u5982\u4e0b\u7684\u6811\u7ed3\u6784\uff1a    1   \/   2   3 \u5b83\u5c06\u88ab\u5e8f\u5217\u5316\u4e3a {1,2,3} <\/code><\/pre>\n
\u6211\u4eec\u7684\u6570\u636e\u662f\u8fdb\u884c BFS \u904d\u5386\u5f97\u5230\u7684\u3002\u5f53\u4f60\u6d4b\u8bd5\u7ed3\u679c Wrong Answer \u65f6\uff0c\u4f60\u53ef\u4ee5\u4f5c\u4e3a\u8f93\u5165\u8c03\u8bd5\u4f60\u7684\u4ee3\u7801\u3002 \u4f60\u53ef\u4ee5\u91c7\u7528\u5176\u4ed6\u7684\u65b9\u6cd5\u8fdb\u884c\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217\u5316\u3002<\/p>\n
[\u9898\u89e3]<\/h1>\n
 <\/p>\n
\u8003\u70b9\uff1a<\/p>\n
    \n
  • \u641c\u7d22 \u9898\u89e3\uff1a<\/li>\n
  • serialize()\u91c7\u7528 bfs\uff0c\u5bf9\u5f53\u524d\u4e8c\u53c9\u6811\u641c\u7d22\uff0c\u904d\u5386 vector\uff0c\u5c06\u5f53\u524d\u8282\u70b9\u5de6\u53f3\u513f\u5b50\u4f9d\u6b21\u5b58\u5165 vector\uff0c\u7a7a\u8282\u70b9\u9700\u8981\u5220\u53bb\u3002<\/li>\n
  • deserialize()\u9996\u5148\u5207\u5272\u5b57\u7b26\u4e32\uff0c\u7136\u540e\u7528 isLeftChild \u6807\u8bb0\u662f\u5f53\u524d\u662f\u5de6\u53f3\u513f\u5b50\uff0c\u6570\u5b57\u8f6c\u5316\u4e3a\u5b57\u7b26\u4e32\uff0c\u5b58\u4e3a\u961f\u5217\u9996\u8282\u70b9\u7684\u5de6\u53f3\u513f\u5b50\u3002<\/li>\n<\/ul>\n
    class Solution { public:     \/**      * This method will be invoked first, you should design your own algorithm       * to serialize a binary tree which denote by a root node to a string which      * can be easily deserialized by your own \"deserialize\" method later.      *\/     vector<string> split(const string &str, string delim) {         vector<string> results;         int lastIndex = 0, index;         while ((index = str.find(delim, lastIndex)) != string::npos) {             results.push_back(str.substr(lastIndex, index - lastIndex));             lastIndex = index + delim.length();         }         if (lastIndex != str.length()) {             results.push_back(str.substr(lastIndex, str.length() - lastIndex));         }         return results;     }     string serialize(TreeNode *root) {         if (root == NULL) {             return \"{}\";         }         vector<TreeNode *> q;         q.push_back(root);         for(int  i = 0; i < q.size(); i++) {             TreeNode * node = q[i];             if (node == NULL) {                 continue;             }             q.push_back(node->left);             q.push_back(node->right);         }         while (q[q.size() - 1] == NULL) {                 q.pop_back();         }         string sb=\"\";         sb += \"{\";         sb += to_string(q[0]->val);         for (int i = 1; i < q.size(); i++) {             if (q[i] == NULL) {                 sb += (\",#\");             }              else {                 sb += \",\";                 sb += to_string(q[i]->val);             }         }         sb += \"}\";         return sb;     }     \/**      * This method will be invoked second, the argument data is what exactly      * you serialized at method \"serialize\", that means the data is not given by      * system, it's given by your own serialize method. So the format of data is      * designed by yourself, and deserialize it here as you serialize it in       * \"serialize\" method.      *\/     TreeNode * deserialize(string &data) {         \/\/ write your code here         if (data == \"{}\") return NULL;         vector<string> vals = split(data.substr(1, data.size() - 2), \",\");         TreeNode *root = new TreeNode(atoi(vals[0].c_str()));         queue<TreeNode *> Q;         Q.push(root);         bool isLeftChild= true;         for (int i = 1; i < vals.size(); i++) {             if (vals[i] != \"#\") {                 TreeNode *node = new TreeNode(atoi(vals[i].c_str()));                 if (isLeftChild) Q.front()->left = node;                 else Q.front()->right = node;                 Q.push(node);             }             if (!isLeftChild) {                 Q.pop();             }             isLeftChild = !isLeftChild;         }         return root;     } }; <\/code><\/pre>\n
    \u66f4\u591a\u9898\u89e3\u67e5\u770b<\/p>\n<\/p><\/div>\n
     \u5927\u4f6c\u6709\u8a71\u8aaa<\/b> (0<\/span>)        <\/div>\n
     <\/div>\n<\/p><\/div>\n<\/p><\/div>\n
      \n
    • \n","protected":false},"excerpt":{"rendered":"
      \u8c37\u6b4c\u9762\u8bd5\u9898\uff1a\u4e8c\u53c9\u6811\u7684\u5e8f\u5217\u5316\u548c\u53cd\u5e8f\u5217…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[],"tags":[],"_links":{"self":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/150093"}],"collection":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=150093"}],"version-history":[{"count":0,"href":"http:\/\/4563.org\/index.php?rest_route=\/wp\/v2\/posts\/150093\/revisions"}],"wp:attachment":[{"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=150093"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=150093"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/4563.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=150093"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}