Java&C++题解与拓展——leetcode449.序列化和反序列化二叉搜索树【么的新知识】

Question

如题所述

Answer 1

每日一题做题记录，参考官方和三叶的题解题目要求

思路一：先序遍历

用先序遍历得到序列化结果，此时第一个元素就是树的根，便于反序列化；

先将序列化结果拆分成单个元素的数组，然后递归构建BST：

取出当前所遍历子树的根$cur$，找到第一个比$cur$大的值，其所在下标为$j$；

所以$j$左边都比$cur$小，为其左子树，右边都比$cur$大，为其右子树；

递归构建即可。

Javapublic class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null)return null;List<String> list = new ArrayList<>();preOrder(root, list);StringBuilder sb = new StringBuilder();for(int i = 0; i < list.size(); i++) {sb.append(list.get(i));if(i != n - 1)sb.append(",");}return sb.toString();}// 先序遍历void preOrder(TreeNode root, List<String> list) {if(root == null)return ;list.add(String.valueOf(root.val));preOrder(root.left, list);preOrder(root.right, list);}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data == null)return null;String[] sSplit = data.split(",");return DFS(0, sSplit.length - 1, sSplit);}TreeNode DFS(int l, int r, String[] ss) {if(l > r)return null;int j = l + 1, cur = Integer.parseInt(ss[l]);TreeNode res = new TreeNode(cur);while(j <= r && Integer.parseInt(ss[j]) <= cur) // 比当前值大的第一个值j++;res.left = DFS(l + 1, j - 1, ss); // 构建左子树res.right = DFS(j, r, ss); // 构建右子树return res;}}

时间复杂度：序列化复杂度为$O(n)$，其中$n$为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为$O(n^2)$，为一条向左下方延伸的链。

空间复杂度：$O(n)$

C++

【注意地址符】

class Codec {public:// Encodes a tree to a single string.string serialize(TreeNode* root) {vector<string> list;preOrder(root, list);if(list.size() == 0)return "";string res;for(int i = 0; i < list.size() - 1; i++)res.append(list[i] + ",");res.append(list.back());return res;}// 先序遍历void preOrder(TreeNode* root, vector<string> &list) {if(root == nullptr)return ;list.emplace_back(to_string(root->val));preOrder(root->left, list);preOrder(root->right, list);}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data.size() == 0)return nullptr;vector<string> sSplit = split(data);return DFS(0, sSplit.size() - 1, sSplit);}TreeNode* DFS(int l, int r, vector<string> &ss) {if(l > r)return nullptr;int j = l + 1, cur = stoi(ss[l]);TreeNode* res = new TreeNode(cur);while(j <= r && stoi(ss[j]) <= cur) // 比当前值大的第一个值j++;res->left = DFS(l + 1, j - 1, ss); // 构建左子树res->right = DFS(j, r, ss); // 构建右子树return res;}// 以“，”分割字符串vector<string> split(const string &str) {char dec = ',';int pos = 0;int start = 0;vector<string> res;while(pos < str.size()) {while(pos < str.size() && str[pos] == dec)pos++;start = pos;while(pos < str.size() && str[pos] != dec)pos++;if(start < str.size())res.emplace_back(str.substr(start, pos - start));}return res;}};

时间复杂度：序列化复杂度为$O(n)$，其中$n$为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为$O(n^2)$，为一条向左下方延伸的链。

空间复杂度：$O(n)$

思路二：二分查找

和上面一样，只不过在反序列化时，采用二分查找第一个大于当前值的位置。

Javapublic class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null)return null;List<String> list = new ArrayList<>();preOrder(root, list);int n = list.size();StringBuilder sb = new StringBuilder();for(int i = 0; i < n; i++) {sb.append(list.get(i));if(i != n - 1)sb.append(",");}return sb.toString();}// 先序遍历void preOrder(TreeNode root, List<String> list) {if(root == null)return ;list.add(String.valueOf(root.val));preOrder(root.left, list);preOrder(root.right, list);}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data == null)return null;String[] sSplit = data.split(",");return DFS(0, sSplit.length - 1, sSplit);}TreeNode DFS(int l, int r, String[] ss) {if(l > r)return null;int ll = l + 1, rr = r, cur = Integer.parseInt(ss[l]);while(ll < rr) { // 二分找第一个大于当前值int m = ll + rr >> 1;if(Integer.parseInt(ss[m]) > cur)rr = m;elsell = m + 1;}if(Integer.parseInt(ss[rr]) <= cur)rr++;TreeNode res = new TreeNode(cur);res.left = DFS(l + 1, rr - 1, ss); // 构建左子树res.right = DFS(rr, r, ss); // 构建右子树return res;}}

时间复杂度：序列化复杂度为$O(n)$，其中$n$为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为$O(n\log n)$，为一条向左下方延伸的链。

空间复杂度：$O(n)$

C++class Codec {public:// Encodes a tree to a single string.string serialize(TreeNode* root) {vector<string> list;preOrder(root, list);if(list.size() == 0)return "";string res;for(int i = 0; i < list.size() - 1; i++)res.append(list[i] + ",");res.append(list.back());return res;}// 先序遍历void preOrder(TreeNode* root, vector<string> &list) {if(root == nullptr)return ;list.emplace_back(to_string(root->val));preOrder(root->left, list);preOrder(root->right, list);}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data.size() == 0)return nullptr;vector<string> sSplit = split(data);return DFS(0, sSplit.size() - 1, sSplit);}TreeNode* DFS(int l, int r, vector<string> &ss) {if(l > r)return nullptr;int ll = l + 1, rr = r, cur = stoi(ss[l]);while(ll < rr) { // 二分找第一个大于当前值int m = (ll + rr) >> 1;if(stoi(ss[m]) > cur)rr = m;elsell = m + 1;}if(stoi(ss[rr]) <= cur) // 比当前值大的第一个值rr++;TreeNode* res = new TreeNode(cur);res->left = DFS(l + 1, rr - 1, ss); // 构建左子树res->right = DFS(rr, r, ss); // 构建右子树return res;}// 以“，”分割字符串vector<string> split(const string &str) {char dec = ',';int pos = 0;int start = 0;vector<string> res;while(pos < str.size()) {while(pos < str.size() && str[pos] == dec)pos++;start = pos;while(pos < str.size() && str[pos] != dec)pos++;if(start < str.size())res.emplace_back(str.substr(start, pos - start));}return res;}};

时间复杂度：序列化复杂度为$O(n)$，其中$n$为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为$O(n\log n)$，为一条向左下方延伸的链。

空间复杂度：$O(n)$

思路三：后序遍历+栈javapublic class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if(root == null)return null;List<String> list = new ArrayList<>();postOrder(root, list);int n = list.size();StringBuilder sb = new StringBuilder();for(int i = 0; i < n; i++) {sb.append(list.get(i));if(i != n - 1)sb.append(",");}return sb.toString();}// 后序遍历void postOrder(TreeNode root, List<String> list) {if(root == null)return ;postOrder(root.left, list);postOrder(root.right, list);list.add(String.valueOf(root.val));}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if(data == null)return null;String[] sSplit = data.split(",");Deque<Integer> stack = new ArrayDeque<Integer>();for(int i = 0; i < sSplit.length; i++)stack.push(Integer.parseInt(sSplit[i]));return DFS(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);}TreeNode DFS(int low, int up, Deque<Integer> stack) {if(stack.isEmpty() || stack.peek() < low || stack.peek() > up)return null;int cur = stack.pop();TreeNode res = new TreeNode(cur);res.right = DFS(cur, up, stack); // 更大的值构建右子树res.left = DFS(low, cur, stack); // 更小的值构建左子树return res;}}

时间复杂度：序列化和反序列化均为$O(n)$

空间复杂度：$O(n)$

C++class Codec {public:// Encodes a tree to a single string.string serialize(TreeNode* root) {vector<string> list;postOrder(root, list);if(list.size() == 0)return "";string res;for(int i = 0; i < list.size() - 1; i++)res.append(list[i] + ",");res.append(list.back());return res;}// 后序遍历void postOrder(TreeNode* root, vector<string> &list) {if(root == nullptr)return ;postOrder(root->left, list);postOrder(root->right, list);list.emplace_back(to_string(root->val));}// Decodes your encoded data to tree.TreeNode* deserialize(string data) {if(data.size() == 0)return nullptr;vector<string> sSplit = split(data);stack<int> stack;for(auto &s : sSplit)stack.emplace(stoi(s));return DFS(INT_MIN, INT_MAX, stack);}TreeNode* DFS(int low, int up, stack<int>& stack) {if(stack.size() == 0 || stack.top() <low || stack.top() > up)return nullptr;int cur = stack.top();stack.pop();TreeNode* res = new TreeNode(cur);res->right = DFS(cur, up, stack); // 更大的值构建右子树res->left = DFS(low, cur, stack); // 更小的值构建左子树return res;}// 以“，”分割字符串vector<string> split(const string &str) {char dec = ',';int pos = 0;int start = 0;vector<string> res;while(pos < str.size()) {while(pos < str.size() && str[pos] == dec)pos++;start = pos;while(pos < str.size() && str[pos] != dec)pos++;if(start < str.size())res.emplace_back(str.substr(start, pos - start));}return res;}};

时间复杂度：序列化和反序列化均为$O(n)$

空间复杂度：$O(n)$

总结

一道快乐的递归遍历题~

【补觉day，最近拖延症发作】

欢迎指正与讨论！原文：https://juejin.cn/post/7096455775937101861

logo设计

创造品牌价值

¥500元起

APP开发

量身定制，源码交付

¥2000元起

商标注册

一个好品牌从商标开始

¥1480元起

公司注册

注册公司全程代办

¥0元起

查

看

更

多

官方电话官方服务
官方网站八戒财税知识产权八戒服务商企业需求数字市场