樣例:
給出一個測試數(shù)據(jù)樣例， 二叉樹{3,9,20,#,#,15,7}，表示如下的樹結(jié)構(gòu)： 3 / /9 20 / / 15 7輸入{1,#,2}輸出{1,#,2}算法要求:
無解題思路:
需要了解什么是二叉樹，其序列化和反序列化是什么。這道題的序列化和反序列化都是用先序遍歷來進行的。首先，我們需要解析字符串，提取出有用的部分，存在vector容器中，再利用create函數(shù)進行遞歸建立二叉樹。本題的難點在于，解析字符串和輸出字符串的處理。算法如下:
public: string serialize(TreeNode *root) {//反序列化 stringstream data; data << "{"; data << serialize2(root); data << "}"; string temp = data.str(); string::iterator itStr; itStr = temp.end(); itStr-=2; //去除結(jié)尾多余的,和# while (itStr != temp.begin()) { if (*itStr == '#') { temp.erase(itStr); } else if (*itStr == ',') { temp.erase(itStr); } else { break; } itStr--; } return temp; } TreeNode *deserialize(string data) {//序列化 if (data.size() == 2) { return NULL; } int start = data.find('{', 0); int end = data.find(',', 0); nums.clear();//清空容器 string tempStr = data.substr(start + 1, end - start - 1); //如果沒有找到,相當于到了最后一個數(shù)，(start + 1)為數(shù)字位置，（data.size()- start - 2）為數(shù)字長度 if (end == -1) { tempStr = data.substr(start + 1, data.size()- start - 2); } else { tempStr = data.substr(start + 1, end - start - 1); } nums.push_back(tempStr); while (end != -1) { start = end; end = data.find(',', start+1); //如果沒有找到,相當于到了最后一個數(shù)，(start + 1)為數(shù)字位置，（data.size()- start - 2）為數(shù)字長度 if (end == -1) { tempStr = data.substr(start + 1, data.size()- start - 2); } else { tempStr = data.substr(start + 1, end - start - 1); } nums.push_back(tempStr); } it = nums.begin(); TreeNode *root = creat(root); return root; }PRivate: vector<string> nums; vector<string>::iterator it; string serialize2(TreeNode *root) {//遞歸先序遍歷，并返回字符串 // write your code here stringstream data;//此為字符串流，用法語cout,cin相似，集二者為一體,在這里用是為了方便操作 if (root == NULL) { data << "#,"; return data.str(); } data << root->val << ','; data << serialize2(root->left); data << serialize2(root->right); return data.str(); } int stoi(string str) {//字符串轉(zhuǎn)化為整型 int num; stringstream ss;//此為字符串流，用法語cout,cin相似，集二者為一體，在這里用是為了整型轉(zhuǎn)換 ss << *it; ss >> num; return num; } TreeNode *creat(TreeNode *bt) {//先序遍歷，遞歸創(chuàng)建 if (it == nums.end()) {//因為序列化需要將多余的#省略，所以如果字符串結(jié)束，那么代表后面全是空結(jié)點。 return NULL; } if (*it == "#") { it++; return NULL; } else { bt = new TreeNode(stoi(*it)); it++; bt->left = creat(bt->left); bt->right = creat(bt->right); return bt; } }新聞熱點
疑難解答
