311周赛第三题
原题链接：2415. 反转二叉树的奇数层
题目
给你一棵 完美 二叉树的根节点 root ，请你反转这棵树中每个 奇数 层的节点值。
- 例如，假设第 3 层的节点值是
[2,1,3,4,7,11,29,18]，那么反转后它应该变成[18,29,11,7,4,3,1,2]。
反转后，返回树的根节点。
完美 二叉树需满足：二叉树的所有父节点都有两个子节点，且所有叶子节点都在同一层。
节点的 层数 等于该节点到根节点之间的边数。
示例 1：
输入：root = [2,3,5,8,13,21,34] 输出：[2,5,3,8,13,21,34] 解释： 这棵树只有一个奇数层。 在第 1 层的节点分别是 3、5 ，反转后为 5、3 。
示例 2：
输入：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 。
提示：
- 树中的节点数目在范围
[1, 214]内 0 <= Node.val <= 105root是一棵 完美 二叉树
思路：
看了灵神的周赛视频讲解，或多或少有影响
这题有两种方法，都可以做交换值：
- BFS
- DFS
BFS代码
{% tabs categories%}
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
import java.util.*;
class Solution {
public TreeNode reverseOddLevels(TreeNode root) {
/*
如果是空节点直接返回
*/
if (root == null) {
return null;
}
// 队列存入每层的节点
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while (!queue.isEmpty()) {
/*
拿出每层的节点放入列表中，并将下一层的节点放入队列中
*/
int size = queue.size();
List<TreeNode> nodeList = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
nodeList.add(node);
if (node.left != null) {
queue.add(node.left);
queue.add(node.right);
}
}
/*
奇数层，在列表中交换收尾节点的值
*/
if (level == 1) {
int nodeSize = nodeList.size();
for (int i = 0; i < nodeSize / 2; i++) {
int num = nodeList.get(i).val;
nodeList.get(i).val = nodeList.get(nodeSize - i - 1).val;
nodeList.get(nodeSize - i - 1).val = num;
}
}
// 改变奇偶层
level = 1 - level;
}
return root;
}
}
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
from typing import Optional
class Solution:
def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
queue = [root]
level = 1
while queue[0].left:
next = []
for node in queue:
next += [node.left, node.right]
queue = next
if level:
for i in range(len(queue) // 2):
node1, node2 = queue[i], queue[len(queue) - 1 - i]
node1.val, node2.val = node2.val, node1.val
level = 1 - level
return root
{% endtabs %}
DFS代码
{% tabs categories%}
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
import java.util.*;
class Solution {
public TreeNode reverseOddLevels(TreeNode root) {
if (root == null) {
return root;
}
dfs(root.left, root.right, 1);
return root;
}
private void dfs(TreeNode left, TreeNode right, int level) {
if (left == null) {
return;
}
if (level == 1) {
// 如果是奇数层，交换值
int tmp = left.val;
left.val = right.val;
right.val = tmp;
}
dfs(left.left, right.right, 1 - level);
dfs(left.right, right.left, 1 - level);
}
}
- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
from typing import Optional
class Solution:
def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(left, right, level: bool) -> None:
if left is None: return
if level: left.val, right.val = right.val, left.val
dfs(left.left, right.right, not level)
dfs(left.right, right.left, not level)
dfs(root.left, root.right, True)
return root
{% endtabs %}
