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

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

热度指数：18890 时间限制：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，点此查看相关信息

算法知识视频讲解

Python2

牛客213592810号

使用后序遍历即可完成正确的比较，因为子树的root在最后，确保了子树的全部元素均在此之前。

class Solution:
    def postorder(self, root, res):
        if not root:
            return
        self.postorder(root.left, res)
        self.postorder(root.right, res)
        res.append(root.val)
        return

    def isContains(self , root1 , root2 ):
        res_1 = []
        res_2 = []
        self.postorder(root1, res_1)
        self.postorder(root2, res_2)
        print(res_1)
        print(res_2)
        for i in range(len(res_1)):
            if res_1[i] == res_2[0]:
                break
        for j in range(len(res_2)):
            if res_1[i] != res_2[j]:
                return False
            i += 1
        return True

发表于 2022-09-18 09:41:56 回复(0)