题目一:BFS的两种方式
二叉树的层序遍历
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
| vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(root == nullptr) {
return ans;
}
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int size = q.size();
vector<int> temp;
for(int i = 0; i < size; i++) {
TreeNode* node = q.front();
temp.push_back(node->val);
q.pop();
if(node->left) {
q.push(node->left);
}
if(node->right) {
q.push(node->right);
}
}
ans.push_back(temp);
}
return ans;
}
|
题目二:锯齿状遍历
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
| vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if(root == nullptr) {
return ans;
}
queue<TreeNode*> que;
que.push(root);
int flag = 0;
while(!que.empty()) {
int size = que.size();
vector<int> temp;
for(int i = 0; i < size; i++) {
auto t = que.front();
temp.push_back(t->val);
que.pop();
if(t->left) {
que.push(t->left);
}
if(t->right) {
que.push(t->right);
}
}
if(flag == 1){
reverse(temp.begin(), temp.end()); // 与题目一的不同之处:翻转过程
flag = 0;
} else {
flag = 1;
}
ans.push_back(temp);
}
return ans;
}
|
题目三:最大特殊宽度
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
| int widthOfBinaryTree(TreeNode *root) {
queue<TreeNode *> que;
queue<unsigned int> nums;
unsigned int l = 0, r = 0; // 左右边界
unsigned int ans = 0; // 最大宽度
que.push(root);
nums.push(1);
while (!que.empty()) {
int size = que.size();
l = nums.front(); // 更新左边界
for (int i = 0; i < size; i++) {
auto t = que.front();
unsigned int num = nums.front();
que.pop();
nums.pop();
r = num; // 更新右边界
if (t->left) {
que.push(t->left);
nums.push(num * 2);
}
if (t->right) {
que.push(t->right);
nums.push(num * 2 + 1);
}
}
ans = max(ans, r - l + 1);
}
return ans;
}
|
题目四:求二叉树的最大深度和最小深度
最大深度:
1
2
3
4
5
6
| int maxDepth(TreeNode *root) {
if(root == nullptr){
return 0;
}
return max(maxDepth(root->left), maxDepth(root->right));
}
|
最小深度:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int minDepth(TreeNode *root){
if(root == nullptr){
return 0;
}
int ldeep = 1e9;
int rdeep = 1e9;
if(root->left != nullptr){
ldeep = min(ldeep, minDepth(root->left));
}
if(root->riggt != nullptr){
rdeep = min(rdeep, minDepth(root->right));
}
return min(ldeep, rdeep) + 1;
}
|
题目五:二叉树的先序序列化和反序列化
序列化:内存里的二叉树转化为字符串(保存树的结构)
存在前序,后序,层序的序列化,但不存在中序的序列化方法
反序列化:字符串转化为内存里的二叉树(建立树的过程)
序列化:
1
2
3
4
5
6
7
8
| string serialize(TreeNode* root) {
if(root == nullptr){
return "#,";
}
string left = serialize(root->left);
string right = serialize(root->right);
return to_string(root->val) + "," + left + right;
}
|
反序列化:
1
2
3
4
5
6
7
8
9
10
11
| TreeNode* deserialize(string data) {
if(data == "#,"){
return nullptr;
}
int val = stoi(data.substr(0, data.find(",")));
TreeNode* root = new TreeNode(val);
int pos = data.find(",") + 1;
root->left = deserialize(data.substr(pos));
root->right = deserialize(data.substr(pos + data.find(",", pos) - pos));
return root;
}
|
题目六:二叉树按层序列化和反序列化
