难度: Easy
给你两棵二叉树的根节点 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运行时间: 32 ms
内存: 15 MB
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None and q is None:
return True
if p is not None and q is not None and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False
这个题解采用递归的方式来判断两棵二叉树是否相同。首先判断当前两个节点 p 和 q 是否同时为 None，如果是则说明遍历到了叶子节点且两棵树一直相同，返回 True。如果当前两个节点都不为 None 且节点值相同，则递归判断它们的左右子树是否相同。只要有一个节点为 None 或者节点值不同，则说明两棵树不同，返回 False。
时间复杂度: O(min(m,n))
空间复杂度: O(min(h1,h2))
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
# 如果两个节点都为None，说明遍历到了叶子节点且一直相同，返回True
if p is None and q is None:
return True
# 如果两个节点都不为None且节点值相同，递归判断左右子树
if p is not None and q is not None and p.val == q.val:
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
# 其他情况说明两棵树不同，返回False
else:
return False
在递归判断两棵树是否相同时，首先检查两个节点是否都为 None 是为了确认双方都已经遍历到叶子节点的终点，这是终止递归的一个重要条件。如果只检查一个节点是否为 None，无法确保另一个节点同样为 None，这可能导致错误的判断。例如，如果一个树的节点为 None（已经没有子节点），而另一棵树的相应位置还有子节点，显然这两棵树不同。因此，必须检查两个节点是否都为 None，以确保两棵树在结构上的一致性。
递归判断两棵树是否相同时，仅比较节点值是不够的，因为这只能保证当前节点在值上相同，但并不能保证整棵树的结构和所有子节点的值也相同。因此，除了比较当前节点的值，还需要递归地检查左右子树是否也相同，以确保整体结构和所有细节上的一致性。如果只比较节点值，可能会忽略子树结构的不同，导致错误地判断两棵树是相同的。
对于具有大量节点的大树，递归方法确实有可能导致调用栈溢出，特别是在树的深度非常大时。为了避免这种情况，可以采用迭代方法来替代递归。例如，可以使用两个栈或队列来同时迭代遍历两棵树的节点。在每一步中，从栈或队列中取出两个节点进行比较，并将它们的子节点按相同的顺序压入栈或队列中。这种迭代方法不会受到调用栈深度的限制，因此可以有效防止栈溢出问题。