解法一：递归

递归判断子树是否同构，直接比较原树或者交换左右子树后再比较。边界条件为遍历到叶子结点。

  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  5. class Node {
  6.     char val;
  7.     Node left;
  8.     Node right;
  10.     public Node() {
  11.     }
  12. }
  14. public class Main {
  15.     public static void main(String[] args) throws IOException {
  16.         // 读入数据
  17.         BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  19.         final int lenA = Integer.parseInt(reader.readLine());
  20.         Node rootA = buildTree(reader, lenA);
  21.         final int lenB = Integer.parseInt(reader.readLine());
  22.         Node rootB = buildTree(reader, lenB);
  24.         if (lenA != lenB) {
  25.             System.out.println("No");
  26.             return;
  27.         }
  29.         if (dfs(rootA, rootB)) {
  30.             System.out.println("Yes");
  31.         } else {
  32.             System.out.println("No");
  33.         }
  34.     }
  36.     /**
  37.      * 建树
  38.      *
  39.      * @param reader 输入
  40.      * @param len    结点数
  41.      * @return 树的根结点
  42.      * @throws IOException
  43.      */
  44.     private static Node buildTree(BufferedReader reader, int len) throws IOException {
  45.         boolean[] hasFather = new boolean[len];
  46.         String[] strs;
  47.         char val;
  48.         Node left, right;
  49.         int number;
  50.         Node[] tree = new Node[len];
  51.         for (int i = 0; i < len; ++i) {
  52.             tree[i] = new Node();
  53.         }
  54.         for (int i = 0; i < len; ++i) {
  55.             strs = reader.readLine().split(" ");
  56.             val = strs[0].charAt(0);
  57.             if (strs[1].charAt(0) == '-') {
  58.                 left = null;
  59.             } else {
  60.                 number = Integer.parseInt(strs[1]);
  61.                 left = tree[number];
  62.                 hasFather[number] = true;
  63.             }
  64.             if (strs[2].charAt(0) == '-') {
  65.                 right = null;
  66.             } else {
  67.                 number = Integer.parseInt(strs[2]);
  68.                 right = tree[number];
  69.                 hasFather[number] = true;
  70.             }
  71.             tree[i].val = val;
  72.             tree[i].left = left;
  73.             tree[i].right = right;
  75.         }
  77.         Node root = null;
  78.         for (int i = 0; i < len; ++i) {
  79.             if (!hasFather[i]) {
  80.                 root = tree[i];
  81.                 break;
  82.             }
  83.         }
  84.         return root;
  85.     }
  87.     private static boolean dfs(Node rootA, Node rootB) {
  88.         if (rootA == null && rootB == null) {
  89.             return true;
  90.         }
  91.         if (rootA == null || rootB == null) {
  92.             return false;
  93.         }
  94.         boolean isLeafA = (rootA.left == null) && (rootA.right == null);
  95.         boolean isLeafB = (rootB.left == null) && (rootB.right == null);
  96.         if (isLeafA && isLeafB) { // 都是叶子结点
  97.             return rootA.val == rootB.val;
  98.         } else if (isLeafA || isLeafB) { // 其中一个是叶子结点
  99.             return false;
  100.         } else { // 递归判断子树是否同构
  101.             return (dfs(rootA.left, rootB.left) && dfs(rootA.right, rootB.right)) ||
  102.                     (dfs(rootA.left, rootB.right) && dfs(rootA.right, rootB.left));
  103.         }
  104.     }
  105. }