共计 2401 个字符，预计需要花费 7 分钟才能阅读完成。
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实现后果
欢送关注
公众号【书所集录】
正文完
