判断t1树中是否有与t2树完全相同的子树

[编程题]判断t1树中是否有与t2树完全相同的子树

热度指数：19529 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。

子树指一棵树的某个节点的全部后继节点

数据范围：树的节点数满足 $0 < n \le 500000$ ，树上每个节点的值一定在32位整型范围内

进阶：空间复杂度: $O(1)$ ，时间复杂度 $O(n)$

示例1

输入

{1,2,3,4,5,6,7,#,8,9},{2,4,5,#,8,9}

输出

true

备注:

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

Python3

danspace

class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        # write code here        
        def isSameTree(root1, root2):
            # 检查两个数是否相同
            if root1 is None and root2 is None:
                return True 
            if root1 is None or root2 is None or root1.val != root2.val:
                return False 
            return isSameTree(root1.left, root2.left) and isSameTree(root1.right, root2.right)

        # 基础情况：
        # 1）两个都是空
        if root1 is None and root2 is None:
            return True 
        # 2）root1为空，root2非空，返回否
        if root1 is None and root2 is not None:
            return False 
        # 3）root1和root2是相同的树
        if isSameTree(root1, root2):
            return True 
        return self.isContains(root1.left, root2) or self.isContains(root1.right, root2)

发表于 2023-04-26 09:48:51 回复(1)