题目解析
给定二叉树的前序 以及 中序遍历
求出给定二叉树的镜像反转的层次遍历
镜像反转的层次遍历
也就是 根右左
解题思路
可以dfs先递归右子树再去递归左子树
每次递归之前去记录根节点
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = 30;
// 存储中序 以及 前序
static int zhong[] = new int[N + 10], qian[] = new int[N + 10];
// 存储镜像层次遍历的结果
static ArrayList<Integer> tree[] = new ArrayList[N + 10];
// 去在中序中找根节点在哪里
// 将这段分为两份
// 一份左节点
// 一份右节点
static int find(int l, int r, int x)
{
for (int i = l; i <= r; i++)
{
if (zhong[i] == x)
return i - l;
}
return -1;
}
static void dfs(int ql, int qr, int zl, int zr, int ceng)
{
// 前序 或者 中序 的 左边大于右边
// 这样就不是一颗树
if (ql > qr || zl > zr)
return;
// 当前这层添加根节点
tree[ceng].add(qian[ql]);
// 去找分界点在中序的位置
int k = find(zl, zr, qian[ql]);
// 先去递归右子树
dfs(ql + k + 1, qr, zl + k + 1, zr, ceng + 1);
// 再去递归左子树
dfs(ql + 1, ql + k, zl, zl + k - 1, ceng + 1);
}
public static void main(String[] args)
{
int n = sc.nextInt();
for (int i = 1; i <= n; i++)
tree[i] = new ArrayList<Integer>();
for (int i = 1; i <= n; i++)
zhong[i] = sc.nextInt();
for (int i = 1; i <= n; i++)
qian[i] = sc.nextInt();
dfs(1, n, 1, n, 1);
// 存储是否出现过一个
boolean f = false;
for (int i = 1; i <= n; i++)
{
for (int j : tree[i])
{
if (f)
out.print(" ");
out.print(j);
f = true;
}
}
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}