BM39. 序列化二叉树
描述
示例1
输入:
{1,2,3,#,#,6,7}
输出:
{1,2,3,#,#,6,7}
说明:
如题面图示例2
输入:
{8,6,10,5,7,9,11}
输出:
{8,6,10,5,7,9,11}
C++ 解法, 执行用时: 2ms, 内存消耗: 536KB, 提交时间: 2021-12-31
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(!root) return "#"; string str = to_string(root->val) + "!"; char* left = Serialize(root->left); char* right = Serialize(root->right); char* ret = new char[strlen(left)+strlen(right)+str.size()]; strcpy(ret, str.c_str()); strcat(ret, left); strcat(ret, right); return ret; } TreeNode* deserialize(char* str, int &p){ if(str[p] == '#'){ p++; return nullptr; } bool sign = 1; if(str[p] == '-'){ sign = 0; p++; } int val = 0; while(str[p] != '!'){ val = val * 10 + str[p] - '0'; p++; } if(sign == 0) val = -val; p++; TreeNode* root = new TreeNode(val); root->left = deserialize(str, p); root->right = deserialize(str, p); return root; } TreeNode* Deserialize(char *str) { int p = 0; return deserialize(str, p); } };
C++ 解法, 执行用时: 2ms, 内存消耗: 592KB, 提交时间: 2021-12-05
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: string serializehelp(TreeNode *r){ queue<TreeNode*> q; q.push(r); string str = ""; while(!q.empty()){ TreeNode* temp = q.front(); q.pop(); if(r->val <0){ if(str==""){ str = str+"#"; }else{ str = str+",#"; } }else{ if(str==""){ str = str+to_string(temp->val); }else{ str = str+","+to_string(temp->val); } } if(temp->val!=-1&&temp->left){ q.push(temp->left); }else if(temp->val!=-1){ TreeNode *templ = new TreeNode(-1); q.push(templ); } if(temp->right){ q.push(temp->right); }else if(temp->val!=-1){ TreeNode *templ = new TreeNode(-1); q.push(templ); } } return str; } char* Serialize(TreeNode *root) { string s; queue<TreeNode*> qt; qt.push(root); while (!qt.empty()) { // pop operator TreeNode *node = qt.front(); qt.pop(); // process null node if (node == nullptr) { s.push_back('#'); s.push_back(','); continue; } // process not null node s += to_string(node->val); s.push_back(','); // push operator qt.push(node->left); qt.push(node->right); } char *ret = new char[s.length() + 1]; strcpy(ret, s.c_str()); return ret; } TreeNode* Deserialize(char *str) { if (str == nullptr) { return nullptr; } // 可用string成员函数 string s(str); if (str[0] == '#') { return nullptr; } // 构造头结点 queue<TreeNode*> nodes; TreeNode *ret = new TreeNode(atoi(s.c_str())); s = s.substr(s.find_first_of(',') + 1); nodes.push(ret); // 根据序列化字符串再层次遍历一遍,来构造树 while (!nodes.empty() && !s.empty()) { TreeNode *node = nodes.front(); nodes.pop(); if (s[0] == '#') { node->left = nullptr; s = s.substr(2); } else { node->left = new TreeNode(atoi(s.c_str())); nodes.push(node->left); s = s.substr(s.find_first_of(',') + 1); } if (s[0] == '#') { node->right = nullptr; s = s.substr(2); } else { node->right = new TreeNode(atoi(s.c_str())); nodes.push(node->right); s = s.substr(s.find_first_of(',') + 1); } } return ret; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 612KB, 提交时间: 2022-03-13
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { if(root == nullptr) return "#"; string str = to_string(root -> val); str += ','; char* left = Serialize(root -> left); char* right = Serialize(root -> right); char* ch = new char[strlen(left) + strlen(right) + str.size()]; ch = strcpy(ch, str.c_str()); strcat(ch, left); strcat(ch, right); return ch; } TreeNode* Deserialize(char *str) { return deserialize(str); } TreeNode* deserialize(char* &str){ if(*str == '#') { ++str; return nullptr; } int num = 0; while(*str != ',') { num = num * 10 + (*str - '0'); ++str; } ++str; TreeNode* root = new TreeNode(num); root -> left = deserialize(str); root -> right = deserialize(str); return root; } };
C++ 解法, 执行用时: 2ms, 内存消耗: 640KB, 提交时间: 2021-12-13
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; */ class Solution { public: char* Serialize(TreeNode *root) { string s; queue<TreeNode*> qt; qt.push(root); while(!qt.empty()) { TreeNode *node = qt.front(); qt.pop(); if(!node) { s.push_back('#'); s.push_back(','); continue; } s += to_string(node->val); s.push_back(','); qt.push(node->left); qt.push(node->right); } char *ret = new char[s.length() + 1]; strcpy(ret, s.c_str()); return ret; } TreeNode* Deserialize(char *str) { if(!str) return nullptr; string s(str); if(str[0]=='#') return nullptr; queue<TreeNode*> nodes; TreeNode *ret = new TreeNode(atoi(s.c_str())); s = s.substr(s.find_first_of(',')+1); nodes.push(ret); while(!nodes.empty() && !s.empty()) { TreeNode *node = nodes.front(); nodes.pop(); if(s[0]=='#') { node->left = nullptr; s = s.substr(2); } else { node->left = new TreeNode(atoi(s.c_str())); nodes.push(node->left); s = s.substr(s.find_first_of(',')+1); } if(s[0]=='#') { node->right = nullptr; s = s.substr(2); } else { node->right = new TreeNode(atoi(s.c_str())); nodes.push(node->right); s = s.substr(s.find_first_of(',')+1); } } return ret; } };
Go 解法, 执行用时: 2ms, 内存消耗: 1024KB, 提交时间: 2021-12-06
package main import . "nc_tools" import "strings" import "strconv" /* * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * @param root TreeNode类 * @return TreeNode类 */ func Serialize( root *TreeNode ) string { // write code here var ret []string var fn = func(val string){ ret = append(ret, val) } serialize(root,fn) return strings.Join(ret,",") } func serialize(root *TreeNode,fn func(val string)){ if root == nil{ fn("#") return } fn(strconv.Itoa(root.Val)) serialize(root.Left,fn) serialize((root.Right),fn) } func Deserialize( s string ) *TreeNode { // write code here var str = strings.Split(s,",") var fn func()*TreeNode fn = func()*TreeNode{ if str[0] == "#"{ str = str[1:] return nil } valInt,_ := strconv.Atoi(str[0]) str = str[1:] return &TreeNode{ Val:valInt, Left:fn(), Right:fn(), } } return fn() } // func deserialize(s *[]string)*TreeNode{ // if (*s)[0] == "#"{ // (*s) = (*s)[1:] // return nil // } // valInt,_ := strconv.Atoi((*s)[0]) // *s = (*s)[1:] // return &TreeNode{ // Val: valInt, // Left: deserialize(s), // Right: deserialize(s), // } // }