Python recursive + memoization, beats 98%


  • 0
    A
    class Solution(object):
        def generateTrees(self, end):
            self.memo = {}
            if end == 0: return []
            return self.helper(end)
            
        def helper(self, end, start=1):
            if start > end:
                return [ None ]
                
            if (start,end) in self.memo: return self.memo[(start,end)]
                
            res = []
            for i in range(start,end+1):
                left = self.helper(i-1,start)
                right = self.helper(end,i+1)
                for l in left:
                    for r in right:
                        temp = TreeNode(i)
                        temp.left = l
                        temp.right = r
                        res.append(temp)
                        
            self.memo[(start,end)] = res
            return res
    

Log in to reply
 

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