【题解 | 二叉树】给定二叉树的中序遍历和前序遍历，问镜面反转后的层序遍历结果

本文主要是介绍【题解 | 二叉树】给定二叉树的中序遍历和前序遍历，问镜面反转后的层序遍历结果，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

玩转二叉树

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7
1 2 3 4 5 6 7
4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

解题思路

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}
}public class Main {// 构建二叉树public static TreeNode buildTree(int[] inorder, int[] preorder, int inStart, int inEnd, int preStart, int preEnd) {if (inStart > inEnd || preStart > preEnd) {return null;}int rootVal = preorder[preStart];TreeNode root = new TreeNode(rootVal);int rootIndex = 0;for (int i = inStart; i <= inEnd; i++) {if (inorder[i] == rootVal) {rootIndex = i;break;}}int leftSize = rootIndex - inStart;root.left = buildTree(inorder, preorder, inStart, rootIndex - 1, preStart + 1, preStart + leftSize);root.right = buildTree(inorder, preorder, rootIndex + 1, inEnd, preStart + leftSize + 1, preEnd);return root;}// 层序遍历public static List<Integer> levelOrderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();if (root == null) {return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while (!queue.isEmpty()) {TreeNode node = queue.poll();result.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}return result;}// 镜面反转二叉树public static void mirrorTree(TreeNode root) {if (root == null) {return;}// 交换左右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;// 递归镜面反转左右子树mirrorTree(root.left);mirrorTree(root.right);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int[] inorder = new int[N];int[] preorder = new int[N];for (int i = 0; i < N; i++) {inorder[i] = scanner.nextInt();}for (int i = 0; i < N; i++) {preorder[i] = scanner.nextInt();}// 构建二叉树TreeNode root = buildTree(inorder, preorder, 0, N - 1, 0, N - 1);// 镜面反转二叉树mirrorTree(root);// 输出反转后的层序遍历结果List<Integer> result = levelOrderTraversal(root);for (int i = 0; i < result.size(); i++) {System.out.print(result.get(i));if (i < result.size() - 1) {System.out.print(" ");}}scanner.close();}
}