是否同一棵二叉搜索树

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{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

PTA 04-树4 是否同一棵二叉搜索树

思路：

1. Build Tree
2. Judge

package PTA;

import java.util.Scanner;

public class 是否同一棵二叉搜索树 {
	static class Struct {
		int data;
		int left;
		int right;

		public Struct() {
			data = -1;
			left = -1;
			right = -1;
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);

		while (sc.hasNext()) {
			int n = sc.nextInt();
			if (n == 0)
				break;
			int l = sc.nextInt();
			int[] arr1 = new int[n];
			for (int i = 0; i < arr1.length; i++) {
				arr1[i] = sc.nextInt();
			}
			Struct[] structArr1 = bulidTree(arr1);// build tree
			for (int i = 0; i < l; i++) {
				int[] arr2 = new int[n];
				for (int j = 0; j < arr2.length; j++) {
					arr2[j] = sc.nextInt();
				}
				// build tree
				Struct[] structArr2 = bulidTree(arr2);
				// judge
				boolean flag = judge(0, structArr1, 0, structArr2);
				if (flag)
					System.out.println("Yes");
				else
					System.out.println("No");
			}
		}

	}

	private static boolean judge(int root1, Struct[] structArr1, int root2, Struct[] structArr2) {

		// 两个根节点都空
		if (root1 == -1 && root2 == -1)
			return true;

		// 一个根节点空，另一个不空
		if (root1 == -1 || root2 == -1)
			return false;

		// 根节点都不空时，判断根节点
		if (structArr1[root1].data != structArr2[root2].data)
			return false;

		// 判断左子树、右子树
		if (judge(structArr1[root1].left, structArr1, structArr2[root2].left, structArr2)
				&& judge(structArr1[root1].right, structArr1, structArr2[root2].right, structArr2))
			return true;
		return false;
	}

	private static Struct[] bulidTree(int[] arr) {
		Struct[] structArr = new Struct[arr.length];
		for (int i = 0; i < structArr.length; i++) {
			structArr[i] = new Struct();
		}
		// 将所有元素依次插入
		for (int i = 0; i < arr.length; i++) {
			if (i == 0) { // 确定根节点
				structArr[0].data = arr[0];
			} else {
				int prev = -1;
				int cur = 0;
				int key = arr[i];
				structArr[i].data = key;
				while (cur != -1) {// cur位置非空
					if (key > structArr[cur].data) {// 去右边插入
						prev = cur;
						cur = structArr[cur].right;
					} else {// 去左边插入
						prev = cur;
						cur = structArr[cur].left;
					}
				}
				// 已找到插入位置的父亲节点
				if (key > structArr[prev].data)
					structArr[prev].right = i;
				else
					structArr[prev].left = i;
			}
		}
		return structArr;
	}

}