序列化时将空指针也记录下来了,所以在反序列化的时候即使只有前序或者后序的序列也都可以递归出树来。因为遇到序列中的null就会return,可以区分开左右树。如果没记录空那么只有单独的前序或者后序是不能构造出树来的。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ //1.加逗号分隔是因为不一定所有的值都是一位数的,所以必须分割 //2.数字转为string 用to_string方法 //3.vector也有.front()方法获取第一个元素 删除第一个元素用.erase(迭代器) //4.stoi把字符串转为数字输出,超过int上下界会报错,类似的还有atoi //5.str的clear()操作 //6.递归传入vector记得用引用& class Codec { public: string serialize_res; // Encodes a tree to a single string. string serialize(TreeNode* root) { inorder(root); return serialize_res; } void inorder(TreeNode* root) { if(root==NULL) { serialize_res+="#,"; return; } serialize_res+=to_string(root->val)+','; inorder(root->left); inorder(root->right); } TreeNode* rdeserialize(vector<string>& dataArray) { if (dataArray.front() == "#") { dataArray.erase(dataArray.begin()); return nullptr; } TreeNode* root = new TreeNode(stoi(dataArray.front())); dataArray.erase(dataArray.begin()); root->left = rdeserialize(dataArray); root->right = rdeserialize(dataArray); return root; } // Decodes your encoded data to tree. TreeNode* deserialize(string data) { vector<string> dataArray; string str; for(auto i:data) { if(i==',') { dataArray.push_back(str); str.clear(); } else{ str.push_back(i); } } if (!str.empty()) { dataArray.push_back(str); str.clear(); } return rdeserialize(dataArray); } }; // Your Codec object will be instantiated and called as such: // Codec ser, deser; // TreeNode* ans = deser.deserialize(ser.serialize(root));