Recursive python solution

  • 15
    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
            return result

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

  • 2

    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.