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

实现结果

实现结果 | 深度优先搜索

实现结果 | 广度优先搜索

欢迎关注

公众号【书所集录】

LeetCode 100. 相同的树 | Python