Python - recursive solution


  • 0
    J

    Here is python's recursive solution. The list generation could be improved, but it passed the test

    class Solution(object):
        def generateTrees(self, n):
            arr = range(1,n+1)
            self.N = len(arr)
            self.res = []
            return self.genTree(arr)
            #return self.res
            
        def genTree(self,arr):
            if len(arr) == 0:
                return []
                
            if len(arr) == 1:
                return [TreeNode(arr[0])]
    
            res = []
            for k in range(len(arr)):
                lefts = self.genTree(arr[:k])
                rights = self.genTree(arr[k+1:])
                if len(lefts)>0 and len(rights)>0:
                    for l in lefts:
                        for r in rights:
                            node = TreeNode(arr[k])
                            node.left  = l
                            node.right = r
                            res.append(node)
                elif len(lefts) > 0:
                    for l in lefts:
                        node = TreeNode(arr[k])
                        node.left  = l
                        res.append(node)
                else:
                    for r in rights:
                        node = TreeNode(arr[k])
                        node.right  = r
                        
                        res.append(node)
            return res

Log in to reply
 

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