【LeetCode 6182 反转二叉树的奇数层】

题目描述

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

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

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

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

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

来源：力扣（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 。
1
2
3
4
5

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

示例 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 。
1
2
3
4
5

解题思路

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

//层次遍历二叉树
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());
	
}

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