Simple solution in python3


  • 0

    Since one tree can be determined by its preorder and inorder traversal, then we can use that to represent a tree. One trivial thought was to traverse all the node in preorder and inorder way, and use a dictionary to record the appearance time of one specific subtree. the key of that dictionary can be the concat of its preorder and inorder traversal, and the value can be the appearance time.

    To avoid mulitple times of traversing the tree, we just need to record the start and end index of one subtree in both traverse sequence. That procedure can be done in the first traverse time.

    Here is my code in Python3, it should be easily understandable. the time complexisty should be O(n)

    class Solution:
        def findDuplicateSubtrees(self, root):
            """
            :type root: TreeNode
            :rtype: List[TreeNode]
            """
            self.d={}
            a,b=self.encode(root)
            res=self.preorder2(root,self.d,[],a,b)
            return res
        
        def preorder2(self,root,d,res,a,b):
            if root==None:
                return []
            i=root.i
            j=root.j
            k=root.k
            m=root.m
            if a[i:j]+b[k:m] in self.d:
                if self.d[a[i:j]+b[k:m]]==1:
                    res.append(root)
                    self.d[a[i:j]+b[k:m]]=2
            else:
                self.d[a[i:j]+b[k:m]]=1
            res+=self.preorder2(root.left,self.d,[],a,b)
            res+=self.preorder2(root.right,self.d,[],a,b)
            return res
        def encode(self,root):
                a=self.preorder(root,0)
                b=self.inorder(root,0)
                return a,b
        def preorder(self,root,i):
                if root==None:
                    return 'a'
                root.i=i
                ls=self.preorder(root.left,i+len(str(root.val)))
                rs=self.preorder(root.right,i+len(str(root.val))+len(ls))
                root.j=i+len(rs)+len(ls)+len(str(root.val))
                return str(root.val)+ls+rs
        def inorder(self,root,i):
                if root==None:
                    return 'a'
                root.k=i
                ls=self.inorder(root.left,i)
                rs=self.inorder(root.right,i+len(str(root.val))+len(ls))
                root.m=i+len(ls)+len(rs)+len(str(root.val))
                return ls+str(root.val)+rs
       
    

Log in to reply
 

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