Jobdu-1009.Binary Search Tree

Posted on | In

Jobdu-二叉搜索树

Question

题目描述：

判断两序列是否为同一二叉搜索树序列

输入：

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

输出：

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

样例输入：

1
2
3
4
5
2
567432
543267
576342
0

样例输出：

YESNO

源自：2010浙江大学计算机与软件工程研究生机试

Answer

对输入的数字序列构建二叉排序树，并对他们进行前序和中序的遍历，依次比较两次遍历结果是否相同，若相同则说明两颗二叉排序树相同，否则不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import java.util.*;
class Main
{
    static class Node{
        int val;
        Node left;
        Node right;
        public Node(int value){
            this.val = value;
        }
    }
    public static Node construct(String str){
        Node root = new Node(str.charAt(0) - '0');
        for(int i = 1; i < str.length(); i++){
            int value = str.charAt(i) - '0';
            insert(value, root);
        }
        return root;
    }
    public static void insert(int value, Node root){
        Node node = new Node(value);
        Node temp = root;
        while(true){
            if(node.val < temp.val){
                if(temp.left == null){
                    temp.left = node;
                    break;
                }
                else
                    temp = temp.left;
            }
            else if(node.val > temp.val){
                if(temp.right == null){
                    temp.right = node;
                    break;
                }
                else
                    temp = temp.right;
            }
            else //for case "equal"
                break;
        }
    }
    public static void preOrder(Node node, StringBuffer res){
//        System.out.print(node.val + " ");
        res.append(node.val);
        if(node.left != null)
            preOrder(node.left, res);
        if(node.right != null)
            preOrder(node.right, res);
    }
    public static void midOrder(Node node, StringBuffer res){
        if(node.left != null)
            midOrder(node.left, res);
//        System.out.print(node.val + " ");
        res.append(node.val);
        if(node.right != null)
            midOrder(node.right, res);
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner sc = new Scanner(System.in);
        StringBuffer res1 = new StringBuffer();
        while(sc.hasNext()){
            int num = sc.nextInt();
            if(num == 0)
                break;
            String a = sc.next();
            Node root1 = construct(a);
            preOrder(root1,res1);
            midOrder(root1, res1);
            for(int i = 0; i < num; i++){
                StringBuffer res2 = new StringBuffer();
                String b = sc.next();
                Node root2 = construct(b);
                preOrder(root2, res2);
                midOrder(root2, res2);
                System.out.println(res1.toString().equals(res2.toString()) ? "YES" : "NO");
            }
        }
        sc.close();
    }
}