Recursive python solution


  • 15
    S
    class Solution(object):
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n == 0:
                return [[]]
            return self.dfs(1, n+1)
            
        def dfs(self, start, end):
            if start == end:
                return None
            result = []
            for i in xrange(start, end):
                for l in self.dfs(start, i) or [None]:
                    for r in self.dfs(i+1, end) or [None]:
                        node = TreeNode(i)
                        node.left, node.right  = l, r
                        result.append(node)
            return result
    

    Use start/end instead of actual nodes to bosst the program.


  • 2
    C

    This solution will fail the testing case n = 0 since the expected output is [].
    I also provide my own solution here for suggestions.


Log in to reply
 

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