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

发表于

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」。

【每日打卡系列】LeetCode 简单题 200 道

题目描述

给你两棵二叉树的根节点 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 ，若以上条件均不满足，则分别判断两个二叉树的左子树和右子树是否相同。这是一个典型的递归过程，因此可以使用深度优先搜索，递归地判断两个二叉树是否相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
python复制代码# 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。

这就是今天要分享的内容，微信搜 Python新视野，每天带你了解更多有用的知识。更有整理的近千套简历模板，几百册电子书等你来领取哦！另外还有Python小白交流群，如果有兴趣可以通过上面的方式联系我哦！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%