100. 相同的树
题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/same-tree
题目
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1
/ /
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入: 1 1
/
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入: 1 1
/ /
2 1 1 2
[1,2,1], [1,1,2]
输出: false
解题思路
由题意可知，若两个二叉树相同，那么两个树在结构上相同，并且节点具有相同的值。那么，我们可以通过深度优先搜索（DFS）、广度优先搜索（BFS）去判断两个二叉树是否相同。
思路：DFS、BFS
深度优先搜索（DFS）
使用深度优先搜索，遇到的情况及分析如下：
- 当两个二叉树都空时，那么可以判定两个二叉树相同，返回 True；
- 当两个二叉树其中一个为空，而另外一个不为空时，那么两个二叉树一定不同的，返回 False；
- 当两个二叉树都不为空的情况下，要对节点的值进行判断。分别对两个二叉树的根节点，以及根节点的左右子树的值进行判断。若出现不同，则表示两个二叉树不同，返回 False，否则返回 True。
具体的代码见【代码实现 # 深度优先搜索】
广度优先搜索（BFS）
同样的，我们也可以使用广度优先搜索的方法来解决这个问题，这里我们要借助辅助队列，算法具体的过程如下：
- 判断两个二叉树是否同时为空，若是，返回 True；
- 判断两个二叉树是否其中一个为空，另一个不为空，若是，返回 False；
- 当两个二叉树都不为空时，开始广度优先搜索，这里使用队列，分别存储两个二叉树的节点：
- 初始先将两个二叉树的根节点分别放入队列中；
- 出队，对出队的两个节点的值进行比较：
- 当两个节点值不同，那么二叉树一定不同；
- 当两个节点值相同，继续判断二叉树的结构是否相同，也就是当前节点的子节点是否存在为空的情况。同时为空，判定为相同，但当两个节点的子节点仅有一个为空，那么二叉树不同。
- 当两个节点值相同，结构也相同时，将两个节点的非空子节点分别存入队列中。这里需要注意的是，存储时，如果子节点不为空，那么考虑的顺序都为从左到右。
当前面的算法执行结束后，如果队列都为空，那么表示两个二叉树是相同的；如果队列不都为空，那么表明二叉树的结构不同，也就是说两个二叉树不同。
具体的代码见【代码实现 # 广度优先搜索】
代码实现
# 深度优先搜索
# 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: TreeNode, q: TreeNode) -> bool:
def dfs(p, q):
# 两个二叉树都为空的情况
if p == None and q == None:
return True
# 两个二叉树只有一个为空的情况
elif p == None or q == None:
return False
# 二叉树都不为空的情况，比较值
elif p.val == q.val:
# 当根节点的值相同时，往下继续判断左右子树的值
return dfs(p.left, q.left) and dfs(p.right, q.right)
# 值不同，返回 False
return False
return dfs(p, q)
# 广度优先搜索
# 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: TreeNode, q: TreeNode) -> bool:
from collections import deque
# 判断两个二叉树是否为空的情况
if not p and not q:
return True
elif not p or not q:
return False
# 都不为空的情况，使用队列，存储二叉树的节点
# 先将两个根节点入队
queue_p = deque([p])
queue_q = deque([q])
while queue_p and queue_q:
node_p = queue_p.popleft()
node_q = queue_q.popleft()
# 比较值
if node_p.val != node_q.val:
return False
# 比较结构
left_p, right_p = node_p.left, node_p.right
left_q, right_q = node_q.left, node_q.right
# 这里使用异或，直接判断两个为空以及其中一个为空的情况
# ^ 相同返回 0，否则返回 1
# 只有返回 1 的情况才会执行语句，也就是不同返回 False
if (not left_p) ^ (not left_q):
return False
if (not right_p) ^ (not right_q):
return False
# 值与结构相同时，当子节点非空，将子节点按照从左到右的顺序入队
if left_p:
queue_p.append(left_p)
if right_p:
queue_p.append(right_p)
if left_q:
queue_q.append(left_q)
if right_q:
queue_q.append(right_q)
# 最后需要判断队列是否为空
# 如果队列不都为空，那么表明二叉树结构不同
return not queue_p and not queue_q
实现结果
欢迎关注
公众号 【书所集录】
