栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Python

【leetcode】572. 另一棵树的子树(python)

Python 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

【leetcode】572. 另一棵树的子树(python)


思路:
  1. 先整体遍历一遍root,在root上找到与subRoot的根节点相同的节点值,
  2. 再用递归(isSame函数)依次判断root的子树和subRoot的节点值和结构是否一致。

注意测试用例:
[1,1]
[1]
即,可能一棵树上有多个相同的节点值,此时只要root的左孩子1和subRoot匹配,即可返回True

# 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 isSame(self, root, subRoot):
        if not root and not subRoot:
            return True
        if not root or not subRoot or root.val != subRoot.val:
            return False
        return self.isSame(root.left, subRoot.left) and self.isSame(root.right, subRoot.right)

    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root:
            return False
        if root.val == subRoot.val:
            if self.isSame(root, subRoot):  # note测试用例:[1,1][1]  即,可能一棵树上有多个相同的节点值,此时只要root的左孩子1和subRoot匹配,即可返回True
                return True
        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)      
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/917927.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号