Python solution beats 95.49%


  • 0
    2
    class Solution(object):
            def generateTrees(self, n):
                """
                :type n: int
                :rtype: List[TreeNode]
                """
                if n == 0:
                    return []
                return self.generateSubTrees(range(1, n+1))
                    
            def generateSubTrees(self, lst):
                if len(lst) == 0:
                    return [None]
                elif len(lst) == 1:
                    return [TreeNode(lst[0])]
                else:
                    result = []
                    for i, val in enumerate(lst):
                        subtrees_left = self.generateSubTrees(lst[:i])
                        subtrees_right = self.generateSubTrees(lst[i+1:])
                        for left in subtrees_left:
                            for right in subtrees_right:
                                root = TreeNode(val)
                                root.left = left
                                root.right = right
                                result.append(root)
                    return result

Log in to reply
 

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