二叉查找树编码与解码
LeetCode 449 给定一个二叉查找树，实现对该二叉查找树编码与解码功能。编码即将二叉查找树转为字符串，解码即将字符串转为二叉查找树。不限制使用何种编码算法，只需保证当对二叉查找树调用编码功能后可再调用解码功能将其复原。
struct TreeNode{
int val;
TreeNode *left;
TreeNode * right;
TreeNode(int x) : val(x),left(NULL),right(NULL){}
};
class Codec{
public:
string serializer(TreeNode *root){}
TreeNode * deserialize(string data){}
};预备知识：二叉查找树前序遍历与复原
对二叉查找树进行前序遍历，将遍历得到的结果按顺序重新构造为一颗新的二叉查找树，新的二叉查找树与二叉树完全一样
//对二叉树进行前序遍历，将遍历得到的节点收集到node_vec中。
void collect_nodes(TreeNode * node, std::vector<TreeNode *> & node_vec){
if(!node){
return;
}
node_vec.push_back(node);
collect_nodes(node->left, node_vec);
collect_nodes(node->right, node_vec);
}
int main(){
TreeNode a(8);
TreeNode b(3);
TreeNode c(10);
TreeNode d(1);
TreeNode e(6);
TreeNode f(15);
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.right = &f;
std::vector<TreeNode *> node_vec;
collect_nodes(&a, node_vec);
for(int i =0; i < node_vec.size(); i++){
node_vec[i] -> left = NULL;
node_vec[i] -> right = NULL;
}
for(int i =1; i < node_vec.size(); i++){
BST_insert(node_vec[0], node_vec[i]);
}
preorder_print(node_vec[0], 0);
return 0;
}算法思路（解码）
将字符串解码为二叉查找树： 将字符串按照编码时的分隔符“#”，将各个数字诸葛拆分出来，将第一个数字构建为二叉查找树的根节点，后面各个数字构建出的节点按解析时的顺序插入根节点中，返回根节点，即完成解码操作。
整型转为字符串（编码阶段）
利用对整数10取余，可以逐个循环的将一个整数从最低位到最高位拆分出来，在这个过程中每取出一个最低位，就将该数字除以10。每拆分出一个字符，就将这个字符添加到string中，直到该数字为0结束。最后将 string进行反转，就完成了整数转字符串。
void change_int_to_string(int val, std::string &str_val){
std:string tmp;
while(val){
tmp += val % 10 + '0';
val = val / 10;
}
for(int i = tmp.length() -1; i > = 0; i--){
str_val += tmp[i];
}
str_val += '#';
}
void BST_preorder(TreeNode * node, std::string &data){
if(!node){
return;
}
std::string str_val;
change_int_to_string(node->val, str_val);
data += str_val;
BST_preorder(node->left, data);
BST_preorder(node->right, data);
}字符串拆分为整数（解码阶段）
#include<stdio.h>
#include<string>
int main(){
std::string str = "123#456#10000#1#";
int val = 0;
for(int i = 0 ; i < str.length(); i++){
if(str[i] == '#'){
printf("val = %d\n", val);
val = 0;
}
else{
val = val * 10 + str[i] - '0';
}
}
return 0;
}练习
class Codec{
public:
std::string serialize(TreeNode * root){
std::string data;
BST_preorder(root, data);//将root指向的树转为字符串data
}
TreeNode *deserialize(std::string data){
if(data.length() == 0){
return NULL;
}
std::vector<TreeNode *> node_vec;
int val = 0;
for(int i = 0; i < data.length(); i++){
if(data[i] == '#'){
node_vec.push_back(new TreeNode(val));
val = 0;
}
else{
val = val * 10 + data[i] - '0';
}
}
for( int i = 1; i < node_vec.size(); i++){
BST_insert(node_vec[0], node_vec[i]);
}
return node_vec[0];
}
}测试
int main(){
TreeNode a(8);
TreeNode b(3);
TreeNode c(10);
TreeNode d(1);
TreeNode e(6);
TreeNode f(15);
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
Codec solve;
std::string data = solve.serialize(&a);
printf("%s\n", data.c_str());
TreeNode * root = solve.deserialize(data);
preorder_print(root, 0);
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.07.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录