Python solution O(m + n) with KMP thought


  • 0
    T
    # -*- coding:utf-8 -*-
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    def dfs (p, l):
        if p == None:
            l.append(None)
            return
        l.append(p.val)
        dfs(p.left, l)
        dfs(p.right, l)
    
    def getPattern(l):
        N = len(l)
        dp = [0] * N
        for i in xrange(N - 1):
            if l[dp[i]] == l[i + 1]:
                dp[i + 1] = dp[i] + 1
            else:
                dp[i + 1] = 0
        return dp
    
    def solve(l1, l2):
        dp = getPattern(l2)
        j = 0
        i = 0
        while i < len(l1):
            if l2[j] == l1[i]:
                j += 1
                if j == len(l2):
                    return True
                i += 1
            else:
                if j == 0:
                    i += 1
                    continue
                if dp[j - 1] == 0:
                    j = 0
                else:
                    j = dp[j - 1] + 1
        return False
    
    class Solution:
        def isSubtree(self, pRoot1, pRoot2):
            # write code here
            if pRoot2 == None or pRoot2 == None:
                return False
            l1 = []
            l2 = []
            dfs(pRoot1, l1)
            dfs(pRoot2, l2)
            return solve(l1, l2)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.