当前位置：首页 > news >正文

小黑被劝退了，生活学习依然继续的leetcode之旅:572. 另一棵树的子树

news 来源：原创 2024/5/18 20:23:05

小黑代码

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        self.match_sub = False
        # 匹配函数
        def match(node,sub_node):
            # 全部为空
            if not (node or sub_node):
                return True
            # 有一个为空
            if (node==None) ^ (sub_node==None):
                return False
            # val不相等
            if node.val != sub_node.val:
                return False
            match_left = match(node.left,sub_node.left)
            match_right = match(node.right,sub_node.right)
            return match_left and match_right

        def dfs(node):
            if (not node) or self.match_sub:
                return
            if match(node,subRoot):
                self.match_sub = True
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return self.match_sub

在这里插入图片描述

KMP匹配法

# 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 isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        # 树和子树的特殊先序遍历
        pre_root = []
        pre_subRoot = []
        # 获取先序遍历
        def dfs(node, arr):
            if not node:
                arr.append('#')
                return
            arr.append(node.val)
            dfs(node.left, arr)
            dfs(node.right, arr)
        # kmp匹配算法
        def kmp(patt, string):
            # 生成next数组
            i = 1
            next_ = [0]
            prefix_len = 0
            while i < len(patt):
                if patt[i]==patt[prefix_len]:
                    i += 1
                    prefix_len += 1
                    next_.append(prefix_len)
                else:
                    if not prefix_len:
                        next_.append(0)
                        i += 1
                    else:
                        prefix_len = next_[prefix_len-1]
            # 开始匹配
            i = 0
            j = 0
            while i < len(string):
                if string[i]==patt[j]:
                    i += 1
                    j += 1
                else:
                    if not j:
                        i += 1
                    else:
                        j = next_[j-1]
                if j == len(patt):
                    return True
            return False
                    

        # 执行函数,获取先序遍历
        dfs(root, pre_root)
        dfs(subRoot, pre_subRoot)
        
        return kmp(pre_subRoot, pre_root)