二叉搜索树

Java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String s = preOrderString(scanner.next());
        for (int i = 0; i < n; i++) {
            String s1 = preOrderString(scanner.next());
            System.out.println(s.equals(s1)?"YES":"NO");
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    static void creat(TreeNode root, int v){
        if (v<root.val){
            if (root.left==null) root.left = new TreeNode(v);
            else creat(root.left,v);
        }else {
            if (root.right==null) root.right= new TreeNode(v);
            else creat(root.right,v);
        }
    }
    static void preOrder(TreeNode root,StringBuilder builder) {
        if (root != null) {
            builder.append(root.val);
            preOrder(root.left,builder);
            preOrder(root.right,builder);
        }
    }
    
    static String preOrderString(String s){
        char[] tree = s.toCharArray();
        TreeNode root = new TreeNode(tree[0]);
        for (int i = 1; i < tree.length; i++) creat(root,tree[i]);
        StringBuilder builder = new StringBuilder();
        preOrder(root,builder);
        return builder.toString();
    }
}

提供另一种思路：

1、这是一棵二叉排序树，那么第一个数就是树根，先输出树根，将剩下的和树根比较，分成大于树根和小于树根的两堆有序的数。

2、将这两堆树按步骤一递归，(小于树根那堆数中，第一个数就是根节点的左孩子；大于树根那堆数中，第一个数就是根节点的右孩子)

3、如果两个序列的输出结果相同，则这两个序列构成的二叉排序树是一样的。

附代码：

import java.util.ArrayDeque;
import java.util.Scanner;

public class Main {

    //对序列进行前序遍历
    public String printTree(ArrayDeque<Integer> alternativeTree){
        if (alternativeTree.isEmpty()){
            return "";
        }else {
            String result = "";
            int topNode = alternativeTree.poll();
            result += topNode;
            ArrayDeque<Integer> smaller = new ArrayDeque<>();
            ArrayDeque<Integer> larger = new ArrayDeque<>();
            int size = alternativeTree.size();
            for (int i=0;i<size;i++){
                int curNode = alternativeTree.poll();
                if (curNode>topNode){
                    larger.add(curNode);
                }else if(curNode<topNode){
                    smaller.add(curNode);
                }
            }
            return result + printTree(smaller) + printTree(larger);
        }
    }
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        Main instance = new Main();

        //将第一个序列按自定义规则输出
        int judgeNum = Integer.parseInt(input.nextLine());
        String accordingTree = input.nextLine();
        ArrayDeque<Integer> accordingDeque = new ArrayDeque<>();
        for(int j=0;j<accordingTree.length();j++){
            accordingDeque.add(Integer.parseInt(accordingTree.charAt(j)+""));
        }
        String accor = instance.printTree(accordingDeque);

        //将后面需要比较的序列分别按自定义规则输出并将输出结果与第一个序列比较
        for (int i=0;i<judgeNum;i++){
            ArrayDeque<Integer> deque = new ArrayDeque<>();
            String alternative = input.nextLine();
            for (int j=0;j<alternative.length();j++){
                deque.add(Integer.parseInt(alternative.charAt(j)+""));
            }
//            System.out.println(instance.printTree(accordingDeque));
//            System.out.println(instance.printTree(deque));
            //System.out.println(instance.printTree(accordingDeque).equals(instance.printTree(deque))?"YES":"NO");
            System.out.println(accor.equals(instance.printTree(deque))?"YES":"NO");
        }
    }
}