从0开始的秋招刷题路，记录下所刷每道题的题解，帮助自己回顾总结

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] 内
$-10^4$ <= Node.val <= $10^4$

思路一：DFS
特例处理，先比较两个根节点： 如果两节点都为空，返回true； 如果两节点一个为空一个不为空，返回false； 如果两节点值不相同，返回false
如果两个节点值相同，比较左子树和右子树是否相同，这就进入了递归

代码

class Solution {public 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 isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}return false;
}

复杂度分析

时间复杂度：$O(min(m,n))$，m和n分别是两个树的节点数
空间复杂度：$O(min(height1,height2))$，两树高度

思路二：BFS
特例处理：如果两根节点都为空，返回true；如果两根节点一个为空一个不为空，返回false
用两个队列分别存储p树和q树的节点，只要两个队列都非空就进入循环
循环中，先弹出两个队列的节点，如果值不同，直接返回false
接下来比较俩节点的子节点情况，如果俩节点的左子节点和右子节点没有分别都存在或都不存在，返回false
存在的子节点们分别入队
循环结束后，只有当两个队列都为空时才会返回true

代码

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p == null && q == null){return true;}else if(p == null || q == null){return false;}Queue<TreeNode> queue1 = new LinkedList<>();Queue<TreeNode> queue2 = new LinkedList<>();queue1.offer(p);queue2.offer(q);while(!queue1.isEmpty() && !queue2.isEmpty()){TreeNode node1 = queue1.poll();TreeNode node2 = queue2.poll();if(node1.val != node2.val){return false;}if((node1.left != null) ^ (node2.left != null)){return false;}if((node1.right != null) ^ (node2.right != null)){return false;}if(node1.left != null){queue1.offer(node1.left);}if(node1.right != null){queue1.offer(node1.right);}if(node2.left != null){queue2.offer(node2.left);}if(node2.right != null){queue2.offer(node2.right);}}return queue1.isEmpty() && queue2.isEmpty();}
}

复杂度分析

时间复杂度：$O(min(m,n))$
空间复杂度：$O(min(m,n))$