【每日算法打卡】100. 相同的树

题目描述

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：

输入： p = [1,2,3], q = [1,2,3]

输出： true

示例 2：

输入： p = [1,2], q = [1,null,2]

输出： false

示例 3：

输入： p = [1,2,1], q = [1,1,2]

输出： false

提示

• 两棵树上的节点数目都在范围 [0, 100] 内
• -104 <= Node.val <= 104

解题思路

本题适合用深度优先搜索，广度优先搜索较为复杂。 首先如果两个二叉树都为空，则两个二叉树相同，返回 True。如果两个二叉树中有且只有一个为空或是两个二叉树的 val 不相同，则两个二叉树一定不相同，不符合题意，返回 False ，若以上条件均不满足，则分别判断两个二叉树的左子树和右子树是否相同。这是一个典型的递归过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        # 如果p与q都为空，返回True
        if not p and not q:
            return True
        # p与q中有且只有一个为空，或是p与q的 `val` 不相同，返回False
        elif (not p or not q) or (p.val != q.val):
            return False
        # 判断p与q的左子树和右子树是否相同
        else:
            return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
复制代码

• 时间复杂度：O(min(m,n))
• 空间复杂度：O(min(m,n))

今日打卡完成，目前进度 9/200。