首页 > ACM题库 > 九度OJ > 九度-1009-二叉搜索树[解题代码]
2013
12-12

九度-1009-二叉搜索树[解题代码]

题目来源:2010年浙江大学计算机及软件工程研究生机试真题

题目描述:
判断两序列是否为同一二叉搜索树序列
输入:
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。
接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
输出:

如果序列相同则输出YES,否则输出NO

样例输入:
2
567432
543267
576342
0
样例输出:
YES
NO

java 代码如下:
import java.io.BufferedInputStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static int arr[] = new int[1024];
	static int temp[] = new int[1024];
	static int cmp1[],cmp2[];
	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while(s.hasNextInt()){
			int n = s.nextInt();
			if(n==0)
				break;
			Arrays.fill(arr, -1);
			cmp1 = new int[10];
			String str = s.next();
			creatTree(str,arr,cmp1);
			for(int i=0; i<n; i++){
				Arrays.fill(temp, -1);
				cmp2 = new int[10];
				str = s.next();
				creatTree(str,temp,cmp2);
				if(Arrays.equals(cmp1, cmp2))
					System.out.println("YES");
				else
					System.out.println("NO");
			}
		}
	}
	
	static void creatTree(String str,int[] arr,int[] cmp){
		int len = str.length();
		for(int i=0; i<len; i++){
			for(int j=1; j<1024;){
				int temp  = str.charAt(i) - '0';
				if( arr[j] == -1){
					arr[j] = temp;
					cmp[temp] = j;
					break;
				}
				if(temp > arr[j])
					j = 2*j +1;
				else
					j = 2*j;
			}
		}
	}

}

/**************************************************************
	Problem: 1009
	User: coder
	Language: Java
	Result: Accepted
	Time:170 ms
	Memory:16772 kb
****************************************************************/


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。