题目描述

给你一棵完美二叉树的根节点 root ，请你反转这棵树中每个奇数层的节点值。

例如，假设第 3 层的节点值是 [2,1,3,4,7,11,29,18] ，那么反转后它应该变成 [18,29,11,7,4,3,1,2] 。

反转后，返回树的根节点。

完美二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。

节点的层数等于该节点到根节点之间的边数。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reverse-odd-levels-of-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

在这里插入图片描述

输入：root = [2,3,5,8,13,21,34]
输出：[2,5,3,8,13,21,34]
解释：
这棵树只有一个奇数层。
在第 1 层的节点分别是 3、5 ，反转后为 5、3 。

在这里插入图片描述

输入：root = [7,13,11]
输出：[7,11,13]
解释： 
在第 1 层的节点分别是 13、11 ，反转后为 11、13 。

示例 3：

输入：root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
输出：[0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]
解释：奇数层由非零值组成。
在第 1 层的节点分别是 1、2 ，反转后为 2、1 。
在第 3 层的节点分别是 1、1、1、1、2、2、2、2 ，反转后为 2、2、2、2、1、1、1、1 。

解题思路

利用层次遍历将二叉树中的数据点遍历出，在遍历的同时在遍历奇数层时，数据需要倒序加入数组。最终得到经过层次遍历得到的数组。最后将从层次遍历的数据插入到二叉树中。

//层次遍历二叉树
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;int i=0;while (!que.empty()) {int size = que.size();vector<int> vec;// 这里一定要使用固定大小size，不要使用que.size()，因为que.size是不断变化的for (int i = 0; i < size; i++) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}if(i%2==1)//奇数层的需要反序加入数组reverse(vec.begin(),vec.end());i++;result.push_back(vec);}return result;
}//将得到的层次遍历的数据构建啊二叉树
TreeNode* createFullBT_queue(TreeNode *&root, vector<int> numbers, int len) {if(len == 0)return nullptr;else {queue<TreeNode *> Q;int i = 0;root = new TreeNode();root->val = numbers[i++];Q.push(root);while(!Q.empty()) {TreeNode *temp = Q.front();Q.pop();if(i < len) {temp->left = new TreeNode();temp->left->val = numbers[i];Q.push(temp->left);i++;}if(i < len) {temp->right = new TreeNode();temp->right->val = numbers[i];Q.push(temp->right);i++;}}}return root;
}TreeNode* reverseOddLevels(TreeNode* root) {vector<vector<int>> tmp=levelOrder(root);vector<int> datas;for(auto x:tmp)for(auto y:x)datas.push_back(y);TreeNode *newroot=new TreeNode();return createFullBT_queue(newroot,datas,datas.size());}