解法一：建树+递归

两部分任务，首先是建立二叉搜索树，用递归的方法插入新结点，其次是判断两棵是否相同，通过递归地遍历来判断。

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  5. class Node {
  6.     int val;
  7.     Node left;
  8.     Node right;
  10.     public Node() {
  11.     }
  13.     public Node(int val) {
  14.         this.val = val;
  15.     }
  16. }
  18. public class Main {
  19.     public static void main(String[] args) throws IOException {
  20.         // 读入数据
  21.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  23.         String[] strs;
  24.         while (true) {
  25.             strs = reader.readLine().split(" ");
  26.             if (strs[0].equals("0") && (strs.length == 1)) {
  27.                 return;
  28.             }
  29.             int n = Integer.parseInt(strs[0]);
  30.             int len = Integer.parseInt(strs[1]);
  31.             Node base = buildTree(reader, n);
  34.             for (int i = 0; i < len; ++i) {
  35.                 Node root = buildTree(reader, n);
  36.                 if (judge(base, root)) {
  37.                     System.out.println("Yes");
  38.                 } else {
  39.                     System.out.println("No");
  40.                 }
  41.             }
  42.         }
  43.     }
  45.     /**
  46.      * 建树
  47.      *
  48.      * @param reader 输入
  49.      * @param n      结点数
  50.      * @return 树的根结点
  51.      * @throws IOException
  52.      */
  53.     private static Node buildTree(BufferedReader reader, int n) throws IOException {
  54.         String[] strs = reader.readLine().split(" ");
  55.         Node root = new Node(Integer.parseInt(strs[0]));
  56.         int val;
  58.         for (int i = 1; i < n; ++i) {
  59.             val = Integer.parseInt(strs[i]);
  60.             insert(root, val);
  61.         }
  62.         return root;
  63.     }
  65.     /**
  66.      * 向二叉搜索树中插入结点
  67.      *
  68.      * @param root 根结点
  69.      * @param val  待插入的值
  70.      */
  71.     private static void insert(Node root, int val) {
  72.         if ((root.left == null) && (val < root.val)) {
  73.             root.left = new Node(val);
  74.         }
  75.         if ((root.right == null) && (val > root.val)) {
  76.             root.right = new Node(val);
  77.         }
  78.         if (val < root.val) {
  79.             insert(root.left, val);
  80.         }
  81.         if (val > root.val) {
  82.             insert(root.right, val);
  83.         }
  84.     }
  86.     /**
  87.      * 判断两棵数是否相同
  88.      *
  89.      * @param rootA 树A
  90.      * @param rootB 树B
  91.      * @return 相同返回true, 否则返回false
  92.      */
  93.     private static boolean judge(Node rootA, Node rootB) {
  94.         if (rootA == null && rootB == null) {
  95.             return true;
  96.         }
  97.         if (rootA == null || rootB == null) {
  98.             return false;
  99.         }
  100.         if (rootA.val != rootB.val) {
  101.             return false;
  102.         } else {
  103.             return judge(rootA.left, rootB.left) && judge(rootA.right, rootB.right);
  104.         }
  105.     }
  106. }