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

实现后果

欢送关注

公众号【书所集录】