力扣100 相同的树

力扣100 相同的树

题目：

给你两棵二叉树的根节点 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

提示：

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

解题思路：

要判断两棵树是否相同我们首先想到两棵树要相同首先必须是树的结构必须相同且相同结构的节点上的值必须是相同的这时这两棵树才能是相同的。

代码：

/**
 * 判断两棵树是否相同，要判断两颗树是否相同首先如果两棵树的结构不同那么肯定不是相同的
 * 其次如果两棵树的结构相同如果相同结构节点的值不同那么这两棵树也不是相同的
 */
public class BooleanSameTree {
    //1.首先定义一个表示树的节点类
    public static class TreeNode{
        public int value;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            this.value = value;
        }
    }
    //2.定义一个方法判断这两棵树是否相同
    public static boolean isSameTree(TreeNode p,TreeNode q){
        //2.1如果一个树的根节点为空另一个树的根节点不为空那么肯定是不相同的两棵树返回false
        if(p == null ^ q == null){
            return false;
        }
        //2.2如果两棵树的根节点都为空那么返回true
        if (p == null && q == null){
            return true;
        }
        /*
        2.3如果两棵树的根节点都不为空，首先我们要判断两颗树的根节点的值是否相同
        其次再递归的判断两棵树的左节点是否相同，再递归判断两棵树的右节点是否相同
         */
        return p.value == q.value && isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
    }
}