题意：

对于一颗给定的二叉树，我们的任务是反转它的所有奇数层的节点的权值 val（根节点所在层为第 0 层），操作完后返回根节点 root。

思路：

思路一：

dfs 镜像遍历：左子树按照左中右的顺序遍历 右子树按照右中左的顺序遍历

当遍历到 奇数层 的时候，根据镜像遍历的特点，可以发现：当前遍历的两个点就是需要对换的两个点，直接对换即可。

思路二：

bfs 提取遍历过程中的 各层的节点，如果当前层是 奇数层，则反转节点权值即可。

思路二的实现较为巧妙，具体可以参考我之前写的一篇关于 bfs 求二叉树宽度 的博客：二叉树专题–洛谷 P3884 [JLOI2009]二叉树问题。

由于我们只关注层数的奇偶性，因此我们只需设置一个只有 0、1 两种取值的变量 dep，如果为 0 表示偶数层，为 1 表示奇数层，

当奇偶性改变的时候，对变量 dep 异或一个 1 即可。

时间复杂度：

$O(n)$

代码：

代码一：dfs（很短）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:void dfs(tn* a, tn* b, int dep){if(!a) return ;if(dep) swap(a->val, b->val);dfs(a->le, b->ri, dep ^ 1), dfs(a->ri, b->le, dep ^ 1);}TreeNode* reverseOddLevels(TreeNode* root) {dfs(root->le, root->ri, 1);return root;}
};

代码二：bfs（较长）

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {
public:tn* bfs(tn* u){qu<tn*> q; q.push(u), q.push(npt);vc<tn*> level;int dep = 0;while(!q.EP())      {auto tt = q.FT(); q.pop();if(!tt){if(level.EP()) break;if(dep){for(int i = 0, j = level.SZ() - 1; i < j; ++i, --j) swap(level[i]->val, level[j]->val);}dep ^= 1;q.push(npt);level.clear();continue;}level.pb(tt);if(tt->left) q.push(tt->le), q.push(tt->ri);}return u;}TreeNode* reverseOddLevels(TreeNode* root) {return bfs(root);}
};

宏定义代码：

typedef pair<int, int> pii;
typedef long long ll;
typedef double db;
#define x first
#define y second
#define tn TreeNode
#define npt nullptr
#define le left
#define ri right
#define qu queue
#define dq deque
#define vc vector
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define EP() empty()
#define SZ() size()
#define FT() front()
#define pb push_back
#define pf push_front
#define pp pop_back