题目要求
思路一：先序遍历
用先序遍历得到序列化结果，此时第一个元素就是树的根，便于反序列化；
先将序列化结果拆分成单个元素的数组，然后递归构建BST：
取出当前所遍历子树的根$cur$，找到第一个比$cur$大的值，其所在下标为$j$；
所以$j$左边都比$cur$小，为其左子树，右边都比$cur$大，为其右子树；
递归构建即可。
Java
public 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)$
思路二：二分查找
和上面一样，只不过在反序列化时，采用二分查找第一个大于当前值的位置。
Java
public 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; else ll = 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; else ll = 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)$
思路三：后序遍历+栈
java
public 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