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

判断t1树中是否有与t2树完全相同的子树_牛客题霸_牛客网

问题简述

给定彼此独立的两棵二叉树，树上的节点值两两不同，判断 t1 树是否有与 t2 树完全相同的子树。
子树指一棵树的某个节点的全部后继节点（子结构不要求全部后继节点）

思路1：前序遍历

• 定义 dfs(t1, t2) 判断两个树是否相同；

• 然后对 root1 的每个节点操作 dfs；

• 时间复杂度 O(MN)；

Python

class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        
        def dfs(r1, r2):
            if not r1 and not r2: return True
            if not r1 or not r2: return False
            
            return r1.val == r2.val and dfs(r1.left, r2.left) and dfs(r1.right, r2.right)
        
        if not root1: return False
        return dfs(root1, root2) \
            or self.isContains(root1.left, root2) \
            or self.isContains(root1.right, root2)

思路2：前序序列化后进行字符串比较

• 为什么可行？——子树上的点在先序遍历中是连续的。

  另一个树的子树 - 力扣官方题解

• 要点：对空叶节点要填充特殊符号来占位；

• 注意：对树的子结构问题不能用本方法；

  树的子结构_牛客题霸_牛客网

Python

class Solution:
    def isContains(self , root1: TreeNode, root2: TreeNode) -> bool:
        
        def dfs(x, tmp):
            if not x:  # 空节点要填充 #
                tmp.append('#')
                return tmp
            
            tmp.append(str(x.val))
            dfs(x.left, tmp)
            dfs(x.right, tmp)
            return tmp
        
        s1 = ''.join(dfs(root1, []))
        s2 = ''.join(dfs(root2, []))
        return s2 in s1