题目解析
给定二叉树的后序中序 求出该二叉树的前序
解题思路
递归分解后序
在中序中找出根的位置
然后在中序中 根的位置 继续递归
根的位置 两边就是左右子树
还有需要注意
二叉树后序遍历是左右根 而前序遍历是根左右
无法直接从后序递归成前序 所以需要记录他们的下标 以下表从小到大来输出
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = 30;
static int hou[] = new int[N + 10];
static int zhong[] = new int[N + 10];
static TreeMap<Integer, Integer> tr = new TreeMap<Integer, Integer>();
static int n;
static void toqian(int start, int end, int left, int right, int node)
{
if (start > end || left > right)
return;
tr.put(node, hou[end]);
for (int i = left; i <= right; i++)
{
if (zhong[i] == hou[end])
{
toqian(start, start + i - left - 1, left, i - 1, node << 1);
toqian(start + i - left, end - 1, i + 1, right, node << 1 | 1);
}
}
}
public static void main(String[] args)
{
n = sc.nextInt();
for (int i = 1; i <= n; i++)
hou[i] = sc.nextInt();
for (int i = 1; i <= n; i++)
zhong[i] = sc.nextInt();
toqian(1, n, 1, n, 1);
int pos = 0;
for (int i : tr.keySet())
{
if (pos++ != 0)
out.print(" ");
out.print(tr.get(i));
}
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}