讨论/技术交流/分享 | 每日一题打卡任务~ 跟我一起快速做一道题吧/
分享 | 每日一题打卡任务~ 跟我一起快速做一道题吧

阅读大约需要3min

解题思路

这道题目的解题思路分为两步.

  1. 首先要把树 s 从头到尾遍历一遍
    遍历一棵树的方法有很多, 迭代法, 递归. 又分为广度优先搜索和深度优先搜索. 这些遍历方法都可以使用, 目的是挨个去查 s 的节点, 看看 s 的某个节点以及它后续的所有子孙节点, 是不是跟 t 拥有一样的结构.

  2. 在遍历的过程中, 判断两棵树是否一样
    有另外一道题目 100. Same Tree 可以作为参考, 判断两个数是否是一样的树. 这里使用了递归的思想, 深度优先算法, 对 p , q 两个树进行对比, 先对比根节点, 如果根节点不一致, 直接返回False, 再进行递归调用, 检查 p, q 的左子树是否相同, 以及 p, q的右子树是否相同.
    代码如下

class Solution:
    def isSametree(self, p, q):
        if p is None and q is None:
            return True
        
        if not p or not q:
            return False
        
        if p.val != q.val:
            return False
        
        return self.isSametree(p.left, q.left) and self.isSametree(p.right, q.right)

代码

有了以上的两步解题思路, 就很容易写出如下的代码

解法一: 迭代法

class Solution:
    def isSametree(self, p, q):
        if p is None and q is None:
            return True
        
        if not p or not q:
            return False
        
        if p.val != q.val:
            return False
        
        return self.isSametree(p.left, q.left) and self.isSametree(p.right, q.right)

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        stack = [s]
        curr = None
        while len(stack) > 0:
            level = len(stack)

            while level > 0:
                curr = stack.pop()
                if curr.right:
                    stack.append(curr.right)
                if curr.left:
                    stack.append(curr.left)
                if self.isSametree(curr, t):
                    return True 
                level -= 1

        return False

解法二: 递归法

class Solution:
    def isSametree(self, p, q):
        if p is None and q is None:
            return True
        
        if not p or not q:
            return False
        
        if p.val != q.val:
            return False
        
        return self.isSametree(p.left, q.left) and self.isSametree(p.right, q.right)

    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
        if s is None and t is None:
            return True 
        
        if not s or not t:
            return False 
        
        return self.isSametree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)

复杂度分析

  • 时间复杂度: 由于 s 上每个节点都要进行一次深度优先搜索来和 t 匹配, 假设匹配一次的时间代价是 O(t), 则总的时间代价是 O(s*t)
  • 空间复杂度: 假设 s 的深度为 ds, t 的深度为 dt. 任意一个时刻, 栈空间的最大使用代价是max(ds, dt), 因此空间复杂度是 max(ds, dt)

理解不对的地方还请大家多多指教,如果这条题解对你有帮助,欢迎点赞支持,感谢👍👍👍

🎈我建了一个微信打卡群, 目前为止所有的小伙伴都每天完成了任务, 没有一个人拉下~
❤️在我的力扣主页 @niconiconi-12 右上角可以找到如何加入微信打卡群哦~ 跟我们一起打卡, 让自己刷题更轻松!

共 0 个回复
暂无回复