网站建设试用,织梦网站统计,购物网站建设运营需求,海报设计模板网站449. 序列化和反序列化二叉搜索树
题意
给定一棵二叉搜索树#xff0c;实现序列化和反序列化#xff1b;注意 val 范围#xff0c;因此 在序列化时需要插入分隔符分割每个节点的 val#xff1b;要善于利用 二叉搜索树的特性#xff08;中序遍历 递增排序#xff09;实现序列化和反序列化注意 val 范围因此 在序列化时需要插入分隔符分割每个节点的 val要善于利用 二叉搜索树的特性中序遍历 递增排序
解法
前序遍历 中序遍历 可以重构一棵树又由于二叉搜索树自带中序遍历因此在序列化时保存前序遍历由于节点的 val 不一定是个位数所以要在序列化时插入分隔符在反序列化时首先分割字符串得到前序遍历然后通过前序遍历和中序遍历进行二叉搜索树的重构。
/*** 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:void PreOrder(TreeNode* root, string data){if(root nullptr) return;data.append(to_string(root-val) ,); // , 作为分隔符// if(root-left ! nullptr) 递归函数开头就判断了非空的情况因此这里不需要再次判断了PreOrder(root-left, data);// if(root-right ! nullptr) 递归函数开头就判断了非空的情况因此这里不需要再次判断了PreOrder(root-right, data);}// Encodes a tree to a single string.string serialize(TreeNode* root) {string res ;PreOrder(root, res);return res;}vectorint Split(string data) // 将序列化后的 string 进行分割得到每个节点的 val{int idx 0;int curS 0;vectorint ans;while(idx data.size()){if(data[idx] ,){string cur data.substr(curS, idx - curS);ans.emplace_back(stoi(cur));curS idx 1;}idx;}return ans;}TreeNode* ReconstructTree(vectorint data, int s, int t){TreeNode* root new TreeNode(data[s]);int rightIdx -1;// 没有孩子if(s t)return root;// 寻找右孩子的根for(int i s 1; i t; i){if(data[i] root-val){rightIdx i;break;}}if(rightIdx -1) // 没有右孩子{root-right nullptr;// 构建左孩子root-left ReconstructTree(data, s 1, t);}else if(rightIdx s 1) // 没有左孩子{root-left nullptr;// 构建右孩子root-right ReconstructTree(data, s 1, t);}else{// 有左孩子构建左孩子和右孩子root-left ReconstructTree(data, s 1, rightIdx - 1);root-right ReconstructTree(data, rightIdx, t);}return root;}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data ) return nullptr;vectorint intData Split(data);TreeNode* root ReconstructTree(intData, 0, intData.size()-1);return root;}
};// Your Codec object will be instantiated and called as such:
// Codec* ser new Codec();
// Codec* deser new Codec();
// string tree ser-serialize(root);
// TreeNode* ans deser-deserialize(tree);
// return ans;复杂度
时间复杂度O(N)序列化前序遍历每个节点反序列化也是恢复每个节点 空间复杂度O(N)存储序列化后的字符串。
