题目概述(简单难度)
给你两棵二叉树的根节点 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
题目链接：
点我进入leetcode
思路与代码
思路展现
这道题目的思路同样是使用递归来进行
1:首先进行根节点的判断，如果一颗树的根节点为空，一棵树的根节点不为空，就说明这两棵树并不相等，直接返回false即可.
2:如果两棵树的根节点都为空，两者相等，返回true
3:如果两棵树的对应的节点位置处的val值并不相等，直接返回false即可
代码示例
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { //假设此时两棵二叉树对应的节点一个为空，一个不为空，则返回false if(p == null && q != null || p != null && q == null) { return false; } /* 此处的代码适用于两种情况: 1:一开始两棵树的根节点为空，说明这两棵树都是空的,相等返回true. 2:当递归到两棵树对应的叶子节点的左子树和右子树的时候，说明这两棵树对应的叶子节点是相等的,但当其左右子树都为空，此时也应该返回true. */ if(p == null && q == null) { return true; } //注意这里不要写==,因为写了就直接return true后，函数就不递归了 if(p.val != q.val) { return false; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } }
总结
考察对于二叉树递归的思想，也是非常经典的一道题目,希望大家好好学习一下.
时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点数。对两个二叉树同时进行深度优先搜索，只有当两个二叉树中的对应节点都不为空时才会访问到该节点，因此被访问到的节点数不会超过较小的二叉树的节点数。
空间复杂度：O(min(m,n))，其中 m 和 n分别是两个二叉树的节点数。空间复杂度取决于递归调用的层数，递归调用的层数不会超过较小的二叉树的最大高度，最坏情况下，二叉树的高度等于节点数。
