2415. 反转二叉树的奇数层

 

 

【DFS】这个和对称二叉树一样，也是用一个双节点参数的函数来遍历这棵二叉树，在遍历的过程中交换左右两个节点的值即可。

class Solution {// 10:57 5 // dfsvoid dfs(TreeNode left, TreeNode right, int t) {if (left == null) return;if (t % 2 == 1) {int tmp = left.val;left.val = right.val;right.val = tmp;}dfs(left.left, right.right, t + 1);dfs(left.right, right.left, t + 1);}public TreeNode reverseOddLevels(TreeNode root) {dfs(root.left, root.right, 1);return root;}
}

【BFS】BFS就是层次遍历，每次把同一层反转过来就好了。

class Solution {public TreeNode reverseOddLevels(TreeNode root) {if (root == null) return root;Deque<TreeNode> queue = new LinkedList();queue.offer(root);int d = 0;while (!queue.isEmpty()) {int n = queue.size();while (n-- > 0) {TreeNode top = queue.poll();if (top.left != null) queue.offer(top.left);if (top.right != null) queue.offer(top.right);}if (d % 2 == 0) {List<Integer> list = new ArrayList();for (var node: queue) list.add(node.val);int m = list.size() - 1;for (var node: queue) {node.val = list.get(m--);}}d++;}return root;}
}