L2-004 这是二叉搜索树吗?(Java)
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
题目
一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,
- 其左子树中所有结点的键值小于该结点的键值;
- 其右子树中所有结点的键值大于等于该结点的键值;
- 其左右子树都是二叉搜索树。
所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。
给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。
输入格式:
输入的第一行给出正整数 。随后一行给出 个整数键值,其间以空格分隔。
输出格式:
如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果,则首先在一行中输出 YES ,然后在下一行输出该树后序遍历的结果。数字间有 1 个空格,一行的首尾不得有多余空格。若答案是否,则输出 NO。
输入样例 1:
sh
7
8 6 5 7 10 8 11
输出样例 1:
sh
YES
5 7 6 8 11 10 8
输入样例 2:
sh
7
8 10 11 8 6 7 5
输出样例 2:
sh
YES
11 8 10 7 5 6 8
输入样例 3:
sh
7
8 6 8 5 10 9 11
输出样例 3:
sh
NO
sh
代码长度限制 16 KB
时间限制 400 ms
内存限制 64 MB
题解
我们知道,前序遍历的顺序是根左右,而二叉搜索树的左节点值肯定比根节点的小,而右节点的值肯定比根节点的大或者相等,题目中的前序遍历可能是镜像后的结果,那么就反过来,左节点的大于等于根节点的值,右节点的小于根节点的值。根据这种思路,我们就可以利用这一特性,去构建这颗二叉树,并判断其结果是否满足要求。
java
import java.util.*;
// L2-004 这是二叉搜索树吗?
public class Main {
static int[] preorder;
// 对于任一结点,
// 其左子树中所有结点的键值小于该结点的键值;
// 其右子树中所有结点的键值大于等于该结点的键值;
// 其左右子树都是二叉搜索树。
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
preorder = new int[n];
// 原前序串
StringBuilder orignStr = new StringBuilder();
for (int i = 0; i < n; i++) {
preorder[i] = sc.nextInt();
orignStr = orignStr.append(preorder[i] + " ");
}
TreeNode3 root = new TreeNode3(preorder[0]);
// 根据前序遍历
initSearchTree(root, n);
// 7
// 8 6 5 7 10 8 11
StringBuilder preStr = new StringBuilder();
pre(root, preStr);
if (preStr.toString().trim().equals(orignStr.toString().trim())) {
System.out.println("YES");
// YES
// 5 7 6 8 11 10 8
StringBuilder postStr = new StringBuilder();
post(root, postStr);
System.out.println(postStr.toString().trim());
} else {
System.out.println("NO");
}
}
/**
* 初始化二叉搜索树
*
* @param root
*/
private static void initSearchTree(TreeNode3 root, int n) {
// 左节点一定比根节点小
boolean flag = true;
if (preorder.length > 1) {
flag = preorder[0] > preorder[1];
}
for (int i = 1; i < n; i++) {
int val = preorder[i];
TreeNode3 node = new TreeNode3(val);
// 每次从根节点加入
TreeNode3 temp = root;
while (true) {
// 不是镜像
if (flag) {
if (val >= temp.val) {
if (temp.right != null) {
temp = temp.right;
continue;
}
temp.right = node;
break;
} else {
if (temp.left != null) {
temp = temp.left;
continue;
}
temp.left = node;
break;
}
} else {
// 镜像
if (val >= temp.val) {
if (temp.left != null) {
temp = temp.left;
continue;
}
temp.left = node;
break;
} else {
if (temp.right != null) {
temp = temp.right;
continue;
}
temp.right = node;
break;
}
}
}
}
}
/**
* 前序遍历
*
* @param root
* @param sb
*/
private static void pre(TreeNode3 root, StringBuilder sb) {
if (root == null) {
return;
}
sb = sb.append(root.val + " ");
if (root.left != null) {
pre(root.left, sb);
}
if (root.right != null) {
pre(root.right, sb);
}
}
/**
* 后续遍历
*
* @param root
* @param sb
*/
private static void post(TreeNode3 root, StringBuilder sb) {
if (root == null) {
return;
}
if (root.left != null) {
post(root.left, sb);
}
if (root.right != null) {
post(root.right, sb);
}
sb = sb.append(root.val + " ");
}
}
class TreeNode3 {
int val;
TreeNode3 left;
TreeNode3 right;
public TreeNode3(int val) {
this.val = val;
}
}

评论
0 条—
还没有评论,来说第一句