0%

449.序列化和反序列化二叉搜索树

题目

序列化和反序列化二叉搜索树

思路

后序遍历:二叉搜索树可根据后序遍历的结果将其恢复。

序列化:只需要对二叉搜索树进行后序遍历,再将数组编码成字符串即可。

反序列化时,需要先将字符串解码成后序遍历的数组。在将后序遍历的数组恢复成二叉搜索树时,不需要先排序得到中序遍历的数组再根据中序和后序遍历的数组来恢复二叉树,而可以根据有序性直接由后序遍历的数组恢复二叉搜索树。后序遍历得到的数组中,根结点的值位于数组末尾,左子树的节点均小于根节点的值,右子树的节点均大于根节点的值,可以根据这些性质设计递归函数恢复二叉搜索树。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
* 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:

// Encodes a tree to a single string.
string serialize(TreeNode* root) {
string res;
vector<int> arr;
postTraversal(root, arr);
if(arr.size() == 0) return res;
for(int i = 0; i < arr.size(); i++){
res += to_string(arr[i]) + ",";
}
return res.substr(0, res.size() - 1);
}

void postTraversal(TreeNode* root, vector<int> &arr){
if(root == NULL) return ;
postTraversal(root->left, arr);
postTraversal(root->right, arr);
arr.emplace_back(root->val);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
TreeNode* root;
vector<int> arr;
transArr(data, arr);
if(arr.size() == 0) {
root = NULL;
return root;
}
// int n = arr.size();
// root->val = arr[n - 1];
root = dfs(arr);
return root;
}

void transArr(string data, vector<int> &arr){ // 将string 拆分为整数数组
int npc = 0;
for(int i = 0; i < data.size(); i++){
if(i == data.size() - 1){
string str = data.substr(npc, i - npc + 1);
arr.emplace_back(stoi(str));
npc = i + 1;
}
else if(data[i] == ','){
string str = data.substr(npc, i - npc);
arr.emplace_back(stoi(str));
npc = i + 1;
}
}
}
TreeNode* dfs(vector<int> arr){
if(arr.size() == 0){
return NULL;
}
int n = arr.size();
int npc = arr[n - 1];
TreeNode* root = new TreeNode(npc);
if(n == 1) return root;

int x = find(arr, npc); // 寻找最后一个小于 根节点的下标,则x左边的都是该节点的左子树,右边的都是该节点的右子树
if(x >= 0){
root->left = dfs(vector<int>(arr.begin(), arr.begin() + x));
}
if(x <= n - 2){
root-> right = dfs(vector<int>(arr.begin() + x, arr.begin() + n - 1));
}
return root;
}

int find(vector<int> arr, int x){
for(int i = 0; i < arr.size() - 1; i ++){
if(arr[i] > x){
return i;
}
}
return arr.size() - 1;
}
};

// 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),其中 n 是树的节点个数,serialize 需要 O(n) 时间遍历每个点。deserialize 需要 O(n) 时间恢复每个点
  • 空间复杂度:O(n),其中 n 是树的节点个数,serialize 需要 O(n) 空间数组保存每个点的值,递归的深度最深也为 O(n)deserialize 需要 O(n) 空间用数组保存每个点的值,递归的深度最深也为 O(n)

执行用时:36 ms, 在所有 C++ 提交中击败了44.95%的用户

内存消耗:36.3 MB, 在所有 C++ 提交中击败了12.22%的用户

通过测试用例:62 / 62

正在加载今日诗词....