给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例 2：

输入：p = [1,2], q = [1,null,2]
输出：false

示例 3：

输入：p = [1,2,1], q = [1,1,2]
输出：false

解题思路：

先判断两棵树当前节点是否都为空，是则返回true；若只有一棵为空则返回false。接着对比当前节点值，不等则返回false。若当前节点都存在且值相等，就递归比较它们的左子树和右子树，左右子树都相同才返回true，有一边不同就返回false。先处理输入为空的边界情况，返回空树。然后从输入首元素创建根节点并入队列，按层序遍历顺序，依输入内容为节点构建左、右子树（非 “#” 表示有节点，创建并关联后入队列），最终返回根节点。

具体代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;// 定义二叉树节点类
class TreeNode1 {int val;TreeNode left;TreeNode right;TreeNode1(int val) {this.val = val;this.left = null;this.right = null;}
}class Solution3 {public boolean isSameTree(TreeNode p, TreeNode q) {// 如果两棵树当前节点都为空，说明同步遍历到了叶子节点的下一层，认为相同if (p == null && q == null) {return true;}// 如果其中一棵为空，另一棵不为空，结构不同，返回Falseif (p == null || q == null) {return false;}// 如果当前节点的值不相等，返回Falseif (p.val!= q.val) {return false;}// 递归比较左子树和右子树是否相同return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}public class  xiangTongDeShu{public static TreeNode buildTree(String[] input) {if (input == null || input.length == 0) {return null;}// 使用队列辅助构建二叉树LinkedList<TreeNode> queue = new LinkedList<>();TreeNode root = new TreeNode(Integer.parseInt(input[0]));queue.add(root);int index = 1;while (!queue.isEmpty() && index < input.length) {TreeNode current = queue.poll();// 构建左子树if (!input[index].equals("#")) {TreeNode left = new TreeNode(Integer.parseInt(input[index]));current.left = left;queue.add(left);}index++;// 构建右子树if (index < input.length &&!input[index].equals("#")) {TreeNode right = new TreeNode(Integer.parseInt(input[index]));current.right = right;queue.add(right);}index++;}return root;}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);System.out.println("请按照层序遍历顺序输入第一棵二叉树节点值（用空格隔开，空节点用#表示）：");String inputStr1 = scanner.nextLine();String[] inputArray1 = inputStr1.split(" ");TreeNode tree1 = buildTree(inputArray1);System.out.println("请按照层序遍历顺序输入第二棵二叉树节点值（用空格隔开，空节点用#表示）：");String inputStr2 = scanner.nextLine();String[] inputArray2 = inputStr2.split(" ");TreeNode tree2 = buildTree(inputArray2);Solution3 solution3 = new Solution3();boolean result = solution3.isSameTree(tree1, tree2);System.out.println("两棵树是否相同：" + result);scanner.close();}
}

运行截图：