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 = rightclass 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 = rightclass 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

实现后果

欢送关注

公众号 【书所集录】