Iterative, Python solution, DP, 76 ms

  • 0
    class Solution(object):
        def generateTrees(self, n):
            :type n: int
            :rtype: List[TreeNode]
            if not n:
                return []
            dp = [[None for j in xrange(n+1)] for i in xrange(n+2)]
            for i in xrange(1, n+2):
                dp[i][i-1] = [None]
            # l length
            for l in xrange(1, n+1):
                for i in xrange(1, n-l+2):
                    j = i + l - 1
                    dp[i][j] = []
                    for k in xrange(i, j+1):
                        left_subtrees = dp[i][k-1]
                        right_subtrees = dp[k+1][j]
                        for lefttree in left_subtrees:
                            for righttree in right_subtrees:
                                root = TreeNode(k)
                                root.left = lefttree
                                root.right = righttree
            return dp[1][n]

Log in to reply

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