题目解析
给定二叉树的后序遍历 请输出二叉树的层次遍历
解题思路
首先需要知道 后序的遍历是(左 右 根)
然后依照这个顺序去还原二叉树
每次递归找到了根的时候 去存储这个节点
代码
import java.io.*;
import java.util.*;
public class Main
{
static int N = 30;
static int shu[] = new int[N + 10]; // 存储后序遍历
// 后序遍历 (左 右 根)
static int bian[] = new int[N + 10]; // 存储层次遍历
static int n, cnt = 1;
static void dfs(int x)
{
if (x > n)
return;
dfs(x << 1); // 左
dfs(x << 1 | 1); // 右
bian[x] = shu[cnt++]; // 根
}
public static void main(String[] args) throws IOException
{
n = sc.nextInt();
for (int i = 1; i <= n; i++)
shu[i] = sc.nextInt();
dfs(1); // 从 1 开始遍历
for (int i = 1; i <= n; i++)
out.print((i != 1 ? " " : "") + bian[i]);
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}