给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。

例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N(≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。

第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。

简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

输出格式:

对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList; /**
* @author Ethan
* @date 2020/6/18
* 7-4 是否同一棵二叉搜索树 (25分)
*/
public class Main { public static void main(String[] args) throws Exception {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n = (int) in.nval;
Node T = new Node();
ArrayList<String> al = new ArrayList<>();
while (n != 0) {
in.nextToken();
int m = (int) in.nval;
T = buildTree(in, n);
boolean a;
for (int i = 0; i < m; i++) {
Node node = buildTree(in, n);
a = check(T, node);
if (a) {
System.out.println("Yes");
} else {
System.out.println("No");
}
} in.nextToken();
n = (int) in.nval; } } static boolean check(Node n, Node m) {
if (n == null && m == null) {
return true;
} else if ((n == null && m != null) || (n != null && m == null)) {
return false;
} else {
if (n.element == m.element) {
return check(n.left, m.left) && check(n.right, m.right);
} else {
return false;
}
}
} static Node buildTree(StreamTokenizer in, int num) throws IOException {
in.nextToken();
Node root1 = new Node();
root1.element = (int) in.nval;
for (int i = 1; i < num; i++) {
in.nextToken();
int element = (int) in.nval;
insertNode(root1, element);
} return root1;
} static void insertNode(Node root, int element) {
if (element > root.element) {
if (root.right == null) {
Node node = new Node();
node.element = element;
root.right = node;
} else {
insertNode(root.right, element);
}
} else {
if (root.left == null) {
Node node = new Node();
node.element = element;
root.left = node;
} else {
insertNode(root.left, element);
}
}
}
} class Node {
public int element;
public Node right;
public Node left; }
05-12 10:52