| 每日一题做题记录，参考官方和三叶的题解 |
- 题目要求
- 思路一：先序遍历
- Java
- C++
- 思路二：二分查找
- Java
- C++
- 思路三：后序遍历+栈
- java
- C++
- 总结
- 用先序遍历得到序列化结果，此时第一个元素就是树的根，便于反序列化；
- 先将序列化结果拆分成单个元素的数组，然后递归构建BST：
- 取出当前所遍历子树的根 c u r cur cur，找到第一个比 c u r cur cur大的值，其所在下标为 j j j；
- 所以 j j j左边都比 c u r cur cur小，为其左子树，右边都比 c u r cur cur大，为其右子树；
- 递归构建即可。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return null;
List 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 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 ) O(n) O(n)，其中 n n n为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为 O ( n 2 ) O(n^2) O(n2)，为一条向左下方延伸的链。
- 空间复杂度： O ( n ) O(n) O(n)
【注意地址符】
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector 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 &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 sSplit = split(data);
return DFS(0, sSplit.size() - 1, sSplit);
}
TreeNode* DFS(int l, int r, vector &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 split(const string &str) {
char dec = ',';
int pos = 0;
int start = 0;
vector 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) O(n)，其中 n n n为节点数量；反序列时查找第一个比当前值大的值，对每个节点的扫描次数与当前节点所在深度相关，最坏情况为 O ( n 2 ) O(n^2) O(n2)，为一条向左下方延伸的链。
- 空间复杂度： O ( n ) O(n) O(n)
- 和上面一样，只不过在反序列化时，采用二分查找第一个大于当前值的位置。
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return null;
List 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 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 ) O(n) O(n)，其中 n n n为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为 O ( n log n ) O(nlog n) O(nlogn)，为一条向左下方延伸的链。
- 空间复杂度： O ( n ) O(n) O(n)
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector 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 &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 sSplit = split(data);
return DFS(0, sSplit.size() - 1, sSplit);
}
TreeNode* DFS(int l, int r, vector &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 split(const string &str) {
char dec = ',';
int pos = 0;
int start = 0;
vector 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) O(n)，其中 n n n为节点数量；反序列时采用二分查找第一个比当前值大的值，此时最坏情况为 O ( n log n ) O(nlog n) O(nlogn)，为一条向左下方延伸的链。
- 空间复杂度： O ( n ) O(n) O(n)
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if(root == null)
return null;
List 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 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 stack = new ArrayDeque();
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 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) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
vector 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 &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 sSplit = split(data);
stack stack;
for(auto &s : sSplit)
stack.emplace(stoi(s));
return DFS(INT_MIN, INT_MAX, stack);
}
TreeNode* DFS(int low, int up, stack& stack) {
if(stack.size() == 0 || 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 split(const string &str) {
char dec = ',';
int pos = 0;
int start = 0;
vector 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) O(n)
- 空间复杂度： O ( n ) O(n) O(n)
一道快乐的递归遍历题~
【补觉day，最近拖延症发作】
| 欢迎指正与讨论！ |
