反转二叉树 Java代码 （二叉树 中序遍历 层序遍历）【PAT甲级1102】

输入样例：

81 -- -0 -2 7- -- -5 -4 6

输出样例：

3 7 2 6 4 0 5 16 5 7 4 3 2 0 1

算法思路：

要将二叉树翻转，可以先按题意建好树，再递归将每个结点的左右结点都交换，也可以再输入时就直接交换。还需要通过“入度”确定根结点，最后通过dfs中序遍历，bfs层序遍历。

Java代码：

import java.io.*;import java.util.*;public class Main {static int N = 15, idx;static int []l = new int[N];static int []r = new int[N];static int []in = new int[N];static int []le = new int[N];static boolean []vis = new boolean[N];public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());Arrays.fill(l, -1);Arrays.fill(r, -1);for(int i = 0; i < n; i++) { // 输入时直接将左右子树调换String[] split = br.readLine().split(" ");if(!split[0].equals("-")) {r[i] = Integer.parseInt(split[0]);vis[Integer.parseInt(split[0])] = true;}if(!split[1].equals("-")) {l[i] = Integer.parseInt(split[1]);vis[Integer.parseInt(split[1])] = true;}}int root = 0; // 找根结点for(int i = 0; i < n; i++)if(!vis[i]) root = i;dfs(root);idx = 0;bfs(root);System.out.print(le[0]);for(int i = 1; i < n; i++) System.out.print(" " + le[i]);System.out.println();System.out.print(in[0]);for(int i = 1; i < n; i++) System.out.print(" " + in[i]);}public static void dfs(int u) {if(u == -1) return;dfs(l[u]);in[idx++] = u;dfs(r[u]);}public static void bfs(int u) {Queue<Integer> qu = new LinkedList<>();qu.add(u);while(!qu.isEmpty()) {int t = qu.poll();le[idx++] = t;if(l[t] != -1) qu.add(l[t]);if(r[t] != -1) qu.add(r[t]);}}}