inorder+preorder traversal + KMP


  • 0
    S

    Saw many have posted their answers using any two order traversal array(I use preorder and inorder in this example) to decide if one tree is subtree of another.

    Just want to add some extra logic here: After generating traversal arrays, we could apply KMP algorithm to determine if one array exists as other array's subarray. The code(Python) is like the following:

        ...... (code generates inorder and preorder traversal)    
            inorder_exist_subarray = self.existIn(inorder_s, inorder_t)
            preorder_exist_subarray = self.existIn(preorder_s, preorder_t)
            if res1 and res2:
                return True
            else:
                return False
        def build_lps(self, arr):
            index = 0
            i = 1
            res = [0]
            while i < len(arr):
                if arr[i] == arr[index]:
                    index += 1
                    res.append(index)
                    i += 1
                else:
                    if index == 0:
                        res.append(0)
                        i += 1
                    else:
                        index = res[index-1]
            return res
        def existIn(self, arr_s, arr_t):
            lps_t = self.build_lps(arr_t)
            i = 0
            j = 0
            while i < len(arr_s):
                if j == len(arr_t):
                    return True
                if arr_s[i] == arr_t[j]:
                    i += 1
                    j += 1
                else:
                    if j == 0:
                        i += 1
                    else:
                        j = lps_t[j-1]
            if j == len(arr_t):
                return True
            return False
    

Log in to reply
 

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