题目来源:https://leetcode.com/problems/average-of-levels-in-binary-tree/description/

标记难度:Easy

提交次数:1/2

代码效率:99.60%

题意

计算一棵二叉树每层结点的平均值。

分析

这道题和Leetcode 102差不多,不过那道题是层次遍历,这道题是求每层的平均值。具体做法也差不多,至少可以通过BFS和DFS两种做法完成层次遍历。

不过我又被long long int卡了一次,我真是非常容易忘记这一点。

代码

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
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
if (root == nullptr) return {};

vector<double> averages;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
// [2147483647,2147483647,2147483647]
int size = q.size();
long long int sum = 0;
for (int i = 0; i < size; i++) {
TreeNode* x = q.front();
q.pop();
sum += x->val;
if (x->left != nullptr) q.push(x->left);
if (x->right != nullptr) q.push(x->right);
}
averages.push_back((double) sum / size);
}

return averages;
}
};

题目来源:https://leetcode.com/problems/binary-tree-level-order-traversal/description/

标记难度:Medium

提交次数:2/2

代码效率:

  • 未优化的DFS:0.00%
  • 优化过的DFS:98.83%

题意

返回一棵二叉树的层次遍历结果。不同层要分开。

分析

这道题和Leetcode 429差不多,那道题是多叉树遍历,这道题是二叉树遍历,似乎还更简单一些。我参考其中DFS的解法写了一份代码,结果很慢,后来我意识到,vector之间的拷贝可能花了太多时间,还不如记录当前结点的深度,然后直接把结点的值放到对应的层里面,于是就快了很多。[1]

代码

未优化的DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
if (root == NULL) return {};
vector<vector<int>> level;
level.push_back({root->val});
vector<TreeNode*> children = {root->left, root->right};
for (TreeNode* ch: children) {
vector<vector<int>> chLevel = levelOrder(ch);
for (int i = 0; i < chLevel.size(); i++) {
if (i + 1 < level.size())
level[i + 1].insert(level[i + 1].end(), chLevel[i].begin(), chLevel[i].end());
else
level.push_back(chLevel[i]);
}
}
return level;
}
};

优化的DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:

vector<vector<int>> levels;

// just put the node value in levels[depth]
void dfs(TreeNode* root, int depth) {
if (root == NULL) return;
if (depth < levels.size())
levels[depth].push_back(root->val);
else
levels.push_back({root->val});
dfs(root->left, depth+1);
dfs(root->right, depth+1);
}

public:
vector<vector<int>> levelOrder(TreeNode* root) {
dfs(root, 0);
return levels;
}
};

  1. Java Solution using DFS

题目来源:https://codeforces.com/contest/1037/problem/D

提交次数:2/3

题意

给定一棵结点编号从1n的无根树,以及一个BFS序列,问该BFS序列是否为合法的树的BFS序列。保证BFS算法必从结点1开始,但BFS序列的第一个结点未必是1

分析

比赛的时候我想了一种模拟的算法,经过一定的debug之后过了pretest,但后来在大数据量下超时了。


模拟算法

我的模拟算法很简单:

  • 对每个结点,记录它是否已被访问(visited[x])、已被访问的邻居个数(count[x]),以及总邻居个数(degree[x]
  • 用一个队列维护已被访问,但是邻居尚未都被访问的结点
  • 验证BFS序列的第一个结点为1visited[1] = true,并将1入队
  • 顺序枚举BFS序列的其他结点y
    • 验证visited[y] == false
    • 将队列中满足count[x] == degree[x]的结点全部弹出,直到得到第一个还有邻居未被访问的结点x
    • 验证yx的邻居
    • count[x]++count[y] = 1(因为y的邻居x已经被访问过了),并将y入队

问题是如何验证yx的邻居。如果直接在邻接表中顺序查找,则在最坏情况下(1n-1个孩子)上述算法的复杂度是O(n^2),对于n = 200000的数据显然是过不了的。所以要把邻接表排序,然后用二分查找在里面寻找元素,这样复杂度在最坏情况下也降低到了O(n * log(n))

构造算法

题解[1]中给出了另一种构造算法:

  • 将每个结点的邻居按它们在BFS序列中出现的顺序排序
  • 按上述排序之后的顺序进行一次BFS
  • 比较两次BFS得到的结点序列是否相同

这种做法的正确性在于,事实上,决定BFS结果的是访问每个结点的子结点的顺序,而这一访问顺序和在BFS中出现的顺序显然是相同的。[2]

排序的时间复杂度最坏是O(n * log(n)),BFS的时间是O(n),总时间复杂度和上一种差不多,但写出来的代码比上一种简洁很多。

代码

模拟算法

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n, x, y;
cin >> n;
vector<vector<int>> graph(n + 1, vector<int>());
int bfs[n + 1];
int marked[n + 1];
bool visited[n + 1];
queue<int> q;
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
graph[x].push_back(y);
graph[y].push_back(x);
}
// 邻接表排序
for (int i = 1; i <= n; i++)
sort(graph[i].begin(), graph[i].end());

for (int i = 0; i < n; i++)
scanf("%d", &bfs[i]);
if (bfs[0] != 1) {
cout << "No" << endl;
return 0;
}
memset(marked, 0, sizeof(marked));
memset(visited, 0, sizeof(visited));
visited[1] = true;
q.push(1);
bool ok = true;
for (int i = 1; i < n; i++) {
int x;
if (q.empty()) {
ok = false;
break;
}
while (!q.empty()) {
x = q.front();
if (marked[x] == graph[x].size())
q.pop();
else
break;
}
int y = bfs[i];
if (visited[y]) {
ok = false;
break;
}
visited[y] = true;
// 寻找孩子结点
auto idx = lower_bound(graph[x].begin(), graph[x].end(), y);
if (idx == graph[x].end() || *idx != y) {
ok = false;
break;
}
marked[x]++;
marked[y] = 1;
q.push(y);
}

if (!ok)
cout << "No" << endl;
else
cout << "Yes" << endl;

return 0;
}

构造算法

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
// 参考:https://codeforces.com/contest/1037/submission/42406857
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> adj[200005];
int bfs[200005];
int ans[200005];
int pos[200005];
bool visited[200005];

int cmp(int x, int y) {
return pos[x] < pos[y];
}

int main() {
int n, x, y;
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i < n; i++) {
cin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 0; i < n; i++) {
cin >> bfs[i];
pos[bfs[i]] = i;
}
// 按结点出现顺序为邻接表排序
for (int i = 1; i <= n; i++)
sort(adj[i].begin(), adj[i].end(), cmp);

// 普通的BFS
int m = 0;
queue<int> q;
visited[1] = true;
q.push(1);
ans[m++] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int child: adj[x])
if (!visited[child]) {
visited[child] = true;
ans[m++] = child;
q.push(child);
}
}

for (int i = 0; i < n; i++) {
if (ans[i] != bfs[i]) {
cout << "No" << endl;
return 0;
}
}
cout << "Yes" << endl;
return 0;
}

  1. Manthan, Codefest'18, IIT (BHU) Editorial

  2. 官方代码