題目描述

請實現兩個函數，分別用來序列化和反序列化二叉樹。

題目思路

在劍指offer中是采用的流的形式進行編寫，這里將二叉樹序列化為字符串，反序列化的時候將字符串反序列化為二叉樹。序列化的時候用了 C++中現成的string數據結構，就不用擔心空間容量的問題了。

題目代碼

#include <iostream> #include <string> #include <fstream> #include <vector> #include <queue> #include "TreeNode.h" using namespace std; /*題目描述 請實現2個函數，分別用來序列化和反序列化二叉樹。*/ class SolutionSerialize { public:char* Serialize(TreeNode *root) {if (root == nullptr)return nullptr;string *result = new string();SerializeCore(root, *result);return (char*)(*result).data();}void SerializeCore(TreeNode *root, string &result) {if (root == nullptr)result.append("$,");else{result.append(to_string(root->val).data()).append(",");SerializeCore(root->left, result);SerializeCore(root->right, result);}}TreeNode* Deserialize(char *str) {if (str == nullptr)return nullptr;TreeNode* root = nullptr;DeserializeCore(&str, &root);return root;}void DeserializeCore(char** str,TreeNode** root){char* begin = *str;char* sperator = strchr(begin, ',');if (sperator == nullptr)return;int len = sperator - begin;char val[20] = { 0 };strncpy(val, begin, len);*str = sperator + 1;//str指針往后移動if (val[0] == '$')*root = nullptr;else{*root = new TreeNode(atoi(val));DeserializeCore(str, &(*root)->left);DeserializeCore(str, &(*root)->right);}}//分行打印void PrintFromTopToBottom2(TreeNode* root) {//vector<int> result;if (root == nullptr)return;// result;queue<TreeNode*> data;data.push(root);int toBePrinted = 1;int nextLevel = 0;while (!data.empty()){TreeNode* node = data.front();data.pop();toBePrinted--;//result.push_back(node->val);cout << node->val << " ";if (node->left != nullptr){data.push(node->left);nextLevel++;}if (node->right != nullptr){data.push(node->right);nextLevel++;}if (toBePrinted == 0){toBePrinted = nextLevel;nextLevel = 0;cout << endl;}}return;// result;} };int main(int argc, char *argv[]) {/*52 8 1 3 6 9*/SolutionSerialize solution;TreeNode t1(5);TreeNode t2(2); t1.left = &t2;TreeNode t3(8); t1.right = &t3;TreeNode t4(1); t2.left = &t4;TreeNode t5(3); t2.right = &t5;TreeNode t6(6); t3.left = &t6;TreeNode t7(9); t3.right = &t7;char* result = solution.Serialize(&t1);cout << result << endl;TreeNode *pRoot = solution.Deserialize(result);solution.PrintFromTopToBottom2(pRoot);return 0; }

測試驗證

總結

以上是生活随笔為你收集整理的C/C++面试题—序列化二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。