LeetCode 449
Serialize and Deserialize BST
- Problem Description:
给出一棵二叉搜索树,将其转换成string类型,并能根据该string字符串还原成原二叉搜索树。其中,对于string字符串的输出没有限制。
具体的题目信息:
https://leetcode.com/problems/serialize-and-deserialize-bst/description/
- Solution:
-
解题思路:
(1)通过层次遍历保存每一层结点值
(2)递归构造二叉搜索树,特别要注意根节点位置的保存
- 编程实现:
-
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Codec {
public:
// Encodes a tree to a single string.
//层次遍历存储二叉树所有结点的值
string serialize(TreeNode* root) {
string result = "";
if (root == NULL) return result;
TreeNode* node[];
int front = -, rear = -, last = ;
vector<int> num;
node[++rear] = root;
while(front<rear) {
TreeNode* p = node[++front];
num.push_back(p->val);
if(p->left)
node[++rear] = p->left;
if (p->right)
node[++rear] = p->right;
if (front == last) {
last = rear;
}
}
for (int i = ; i < num.size(); i++) {
if (i != ) {
result += "-";
}
stringstream sstr;
sstr << num[i];
result += sstr.str();
}
return result;
}
// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode* root = NULL;
TreeNode* p = NULL;
vector<int> num;
string temp = "";
int x;
if (data == "") return root;
for (int i = ; i < data.length(); i++) {
if (data[i] != '-') {
temp += data[i];
if (i == data.length()-) {
//将数字转换成字符串
stringstream pstr(temp);
pstr >> x;
num.push_back(x);
}
} else {
stringstream sstr(temp);
sstr >> x;
num.push_back(x);
temp = "";
}
}
root = new TreeNode(num[]);
int j = , count = num.size();
while(j < count) {
InsertBST(root, num[j]);
j++;
}
return root;
}
//递归插入构造二叉搜索树
void InsertBST(TreeNode* p, int val) {
if (val > p->val) {
if (p->right == NULL)
p->right = new TreeNode(val);
else
InsertBST(p->right, val);
} else {
if (val < p->val) {
if (p->left == NULL)
p->left = new TreeNode(val);
else
InsertBST(p->left, val);
}
}
}
};
// Your Codec object will be instantiated and called as such:
// Codec codec;
// codec.deserialize(codec.serialize(root));