Java 题解 | #牛群的相似结构#

该题考察的主要知识点包括：

1. 二叉树的遍历：深度优先搜索（DFS）是一种遍历二叉树的方法，通过递归或栈的方式，可以遍历树的所有节点。
2. 递归：在判断两个二叉树的结构是否相同时，使用了递归的方式，递归是解决树相关问题的常用技巧。
3. 字符串的比较：为了判断两个二叉树的结构是否相同，将树的结构表示为字符串，并通过字符串的比较来判断是否相同。

代码解释大纲：

1. 定义二叉树节点类 TreeNode，包含 val 表示牛的编号，left 表示左子节点，right 表示右子节点。
2. 编写一个 Solution 类，包含一个 isSameCowStructure 方法，用于判断两个牛群的结构是否相同。
3. isSameCowStructure 方法接收两个参数 root1 和 root2，分别代表两个牛群的根节点。
4. 在 isSameCowStructure 方法内部，调用 getTreeStructure 方法获取两个牛群的结构表示，然后通过字符串的比较来判断是否相同，并返回结果。
5. getTreeStructure 方法是一个递归方法，用于将二叉树表示为字符串。如果节点为空，则用 # 表示，否则使用节点的值作为字符串的一部分，并继续递归处理左右子节点。

总体来说，代码利用深度优先搜索遍历两个二叉树，将它们的结构表示为字符串，然后通过字符串的比较来判断这两个牛群的结构是否相同。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param p TreeNode类
     * @param q TreeNode类
     * @return bool布尔型
     */
    public boolean isSameTree (TreeNode p, TreeNode q) {
        // write code here
        String tree1 = isSameTree(p);
        String tree2 = isSameTree(q);

        return tree1.equals(tree2);
    }

    // 使用DFS将二叉树表示为字符串
    private String isSameTree(TreeNode root) {
        if (root == null) {
            return "#";
        }

        StringBuilder sb = new StringBuilder();
        sb.append(root.val);
        sb.append(isSameTree(root.left));
        sb.append(isSameTree(root.right));

        return sb.toString();
    }
}