相同的二叉树

给你两棵二叉树的根节点 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;
        }
        // 如果其中一棵为空，另一棵不为空，结构不同，返回False
        if (p == null || q == null) {
            return false;
        }
        // 如果当前节点的值不相等，返回False
        if (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();
    }
}

运行截图：