经典Java面试题解析：判断两个二叉树是否相同

在Java的面试中，判断两个二叉树是否相同是一个常见的算法问题。本文将介绍一道经典的Java面试题——判断两个二叉树是否相同，并提供详细的解析和解题思路。

题目

给定两个二叉树，判断它们是否相同（即结构相同且节点的值相同）。

解析与解题思路

判断两个二叉树是否相同可以使用递归的方式来实现。

1. 如果两个二叉树都为空，则它们相同，返回true。
2. 如果两个二叉树中有一个为空而另一个不为空，则它们不相同，返回false。
3. 如果两个二叉树的根节点的值不相同，则它们不相同，返回false。
4. 否则，递归地判断两个二叉树的左子树和右子树是否相同。

以下是Java代码实例：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}

public class SameTree {
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true; // 两个二叉树都为空，相同
        } else if (p == null || q == null) {
            return false; // 一个二叉树为空，一个二叉树不为空，不相同
        } else if (p.val != q.val) {
            return false; // 两个二叉树的根节点值不相同，不相同
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 递归判断左子树和右子树是否相同
        }
    }

    public static void main(String[] args) {
        /*
         * 构造两个二叉树：
         *  二叉树1：
         *      1
         *     / \
         *    2   3
         *
         *  二叉树2：
         *      1
         *     / \
         *    2   3
         */
        TreeNode p = new TreeNode(1);
        p.left = new TreeNode(2);
        p.right = new TreeNode(3);

        TreeNode q = new TreeNode(1);
        q.left = new TreeNode(2);
        q.right = new TreeNode(3);

        boolean result = isSameTree(p, q);
        System.out.println("两个二叉树是否相同：" + result);
    }
}

输出结果：

两个二叉树是否相同：true

结论

通过递归的方式，我们可以判断两个二叉树是否相同。判断二叉树相同的条件是：两个二叉树的根节点值相同，并且它们的左子树和右子树也相同。掌握了解题思路和实现代码，我们能够在面试中更加自信地回答相关问题。

  学java，就到java编程狮！