题目描述：
给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。
- 例如，假设第 3 层的节点值是
[2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。
反转后，返回树的根节点。
完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
节点的 层数 等于该节点到根节点之间的边数。
数据范围：
$1\le n \le 2^{14}$
题解：
bfs：
直接层次遍历，把奇数层的存起来，然后翻转。
dfs:
传入两个指针，表示可能需要交换的节点。然后每次按照对称顺序继续遍历。
代码：
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
TreeNode *reverseOddLevels(TreeNode *root)
{
queue<TreeNode *> q;
q.push(root);
int dep = 0;
while (q.size())
{
int size = q.size();
dep++;
if (dep & 1)
{
vector<TreeNode *> v;
for (int i = 0; i < size; ++i)
{
auto out = q.front();
v.emplace_back(out);
q.pop();
if (!out->left)
q.push(out->left);
if (!out->right)
q.push(out->right);
}
for (int i = 0; i < v.size() / 2; ++i)
{
swap(v[i]->val, v[v.size() - i - 1]->val);
}
}
else
{
for (int i = 0; i < size; ++i)
{
auto out = q.front();
q.pop();
if (!out->left)
q.push(out->left);
if (!out->right)
q.push(out->right);
}
}
}
return root;
}
};
|
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
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
void dfs(TreeNode *left, TreeNode *right, bool flag)
{
if (left == nullptr)
return;
if (flag)
swap(left->val, right->val);
dfs(left->left, right->right, !flag);
dfs(left->right, right->left, !flag);
}
TreeNode *reverseOddLevels(TreeNode *root)
{
dfs(root->left, root->right, true);
return root;
}
};
|