当前位置：首页 > news >正文

进阶：反转二叉树的奇数层

news 来源：原创 2024/9/27 5:27:54

目录标题

- - 题目描述
  - 示例
  - 解题思路
  - 代码实现
  - 详细步骤解释
  - 复杂度分析

题目描述

给定一棵完美二叉树的根节点 root，请反转这棵树中每个奇数层的节点值。完美二叉树是指所有叶子节点都在同一层，并且每个非叶子节点都有两个子节点。

示例

示例 1：
输入：

     2/   \3     5/ \   / \
7   8 10  11

输出：

     2/   \5     3/ \   / \
7   8 10  11

示例 2：
在这里插入图片描述

解题思路

层次遍历：使用层次遍历来访问每一层的节点。
奇数层处理：在遍历过程中，对于奇数层（从 1 开始计数），我们需要反转该层的节点值。
交换节点值：对于奇数层的节点，我们可以使用双指针方法来交换节点的值。

代码实现

import java.util.LinkedList;
import java.util.Queue;public class Solution {public TreeNode reverseOddLevels(TreeNode root) {if (root == null) {return null;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int level = 0;while (!queue.isEmpty()) {int size = queue.size();if (level % 2 == 1) {  // 奇数层// 反转当前层的节点值for (int i = 0; i < size / 2; i++) {TreeNode leftNode = queue.poll();TreeNode rightNode = queue.poll();// 交换节点值int temp = leftNode.val;leftNode.val = rightNode.val;rightNode.val = temp;// 将子节点加入队列if (leftNode.left != null) {queue.offer(leftNode.left);queue.offer(rightNode.right);}if (leftNode.right != null) {queue.offer(leftNode.right);queue.offer(rightNode.left);}}} else {  // 偶数层for (int i = 0; i < size; i++) {TreeNode node = queue.poll();if (node.left != null) {queue.offer(node.left);queue.offer(node.right);}}}level++;}return root;}public static void main(String[] args) {// 构建示例二叉树TreeNode root = new TreeNode(2);root.left = new TreeNode(3);root.right = new TreeNode(5);root.left.left = new TreeNode(7);root.left.right = new TreeNode(8);root.right.left = new TreeNode(10);root.right.right = new TreeNode(11);Solution solution = new Solution();TreeNode result = solution.reverseOddLevels(root);// 打印结果printTree(result);}private static void printTree(TreeNode root) {if (root == null) {return;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();System.out.print(node.val + " ");if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}System.out.println();}}
}class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) {val = x;}
}

详细步骤解释

初始化队列：
- 使用一个队列来进行层次遍历，初始时将根节点加入队列。
层次遍历：
- 使用 while 循环进行层次遍历，直到队列为空。
- 每次循环开始时，记录当前层的节点数量 size。
奇数层处理：
- 如果当前层数 level 是奇数（从 1 开始计数），则需要反转该层的节点值。
- 使用双指针方法，从队列中依次取出两个节点，交换它们的值。
- 将这两个节点的子节点按顺序加入队列。
偶数层处理：
- 如果当前层数 level 是偶数，则正常进行层次遍历，将当前层的所有节点的子节点按顺序加入队列。
递增层数：
- 每处理完一层，层数 level 递增 1。
返回结果：
- 最终返回修改后的根节点 root。