Python dynamic programming.

  • 0

    At each node, we try to split a range [start, end] and choose a value as the root. Then the left subtree is assigned the range [start, value - 1] and the right subtree has the range [value + 1, end].
    Once a same range [start, end] is encountered again, we just retrieve it by memoization.

    class Solution(object):
        def generateTrees(self, n):
            :type n: int
            :rtype: List[TreeNode]
            if n < 1:
                return []
            self.memory = [[[] for _ in range(n + 1)] for _ in range(n + 1)]
            return self.buildTrees(1, n)
        def buildTrees(self, start, end):
            if start > end:
                return [None]
            if start == end:
                return [TreeNode(start)]
            if self.memory[start][end]:
                return self.memory[start][end]
            for val in range(start, end+1):
                leftTrees = self.buildTrees(start, val - 1)
                rightTrees = self.buildTrees(val+1, end)
                for left in leftTrees:
                    for right in rightTrees: # note: here we may share left and right for various trees
                        root = TreeNode(val) # but it doesn't affect the results
                        root.left = left
                        root.right = right
            return self.memory[start][end]

Log in to reply

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