题目解析
给定一个二叉树的前序遍历 判断是否为 二叉搜索树 或者 镜像二叉搜索树
是就输出 "YES" 加 后序遍历
否则 输出 "NO"
解题思路
利用二叉搜索树的性质(题目中有给出), 我们每次去找这个二叉树的左子树、右子树以及根节点。
然后利用找出来的左右子树以及根节点推出后序，看后序的个数是否为前序的个数，来判断是否为合法的二叉搜索树
代码
import java.io.*;
import java.math.*;
import java.util.*;
public class Main
{
static int N = (int) 1e3;
static int tree[] = new int[N + 10];
// 存储后序遍历
static ArrayList<Integer> hou = new ArrayList<Integer>();
static int n;
static void pre(int left, int right, boolean f)
{
if (left > right)
return;
// 左子树的范围为 [left + 1, lend)
// 存储左子树结尾的节点
int lend = left + 1;
// 右子树的范围为 (rstart, right]
// 存储右子树开始的节点
int rstart = right;
// 不是镜像二叉搜索树
if (!f)
{
// 左子树所有叶子节点都比根节点小
while (lend <= right && tree[lend] < tree[left])
lend++;
// 右子树所有叶子节点都比根节点大
while (rstart > left && tree[rstart] >= tree[left])
rstart--;
}
// 是镜像二叉搜索树
else
{
// 左子树所有叶子节点都比根节点大
while (lend <= right && tree[lend] >= tree[left])
lend++;
// 右子树所有叶子节点都比根节点小
while (rstart > left && tree[rstart] < tree[left])
rstart--;
}
// 左子树
pre(left + 1, lend - 1, f);
// 右子树
pre(rstart + 1, right, f);
// 前序: 根左右
// 后序: 左右根
// 因为是递归 所以每次完成一个子树的时候都将根节点丢进来
// 注: 最下面一层也算一个子树 只不过没有叶子节点
hou.add(tree[left]);
}
static void print()
{
out.println("YES");
for (int i = 0; i < n; i++)
{
if (i != 0)
out.print(" ");
out.print(hou.get(i));
}
}
public static void main(String[] args)
{
n = sc.nextInt();
for (int i = 1; i <= n; i++)
tree[i] = sc.nextInt();
// 检查 是否为不需要镜像得二叉搜索树
pre(1, n, false);
if (hou.size() == n)
print();
// 否则 就去看 是否为镜像得查查搜索树 如果也不是 就输出 NO
else
{
hou.clear();
// 检查是否为需要镜像的二叉搜索树
pre(1, n, true);
if (hou.size() == n)
print();
// 最后两种情况都不符合就是 NO
else
out.println("NO");
}
out.flush();
out.close();
}
static Scanner sc = new Scanner(System.in);
static PrintWriter out = new PrintWriter(System.out);
}