2 solutions, recursion, and with caching


  • 0
    I

    caching here does not improve the big O complexity, but it will improve runtime cause of reduced recursive calls.

    brute force recursion:

    class Solution(object):
        def gen_trees_util(self, start, end):
            if start > end:
                return [None]
            
            trees = []
            for root in xrange(start, end + 1):
                for l_subtree in self.gen_trees_util(start, root-1):
                    for r_subtree in self.gen_trees_util(root+1, end):
                        curr_root = TreeNode(root)
                        curr_root.left = l_subtree
                        curr_root.right = r_subtree
                        trees.append(curr_root)
                        
            return trees
            
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n < 1:
                return []
            return self.gen_trees_util(1, n)
    

    with caching:

    class Solution(object):
        def gen_trees_util(self, start, end, tree_cache):
            if start > end:
                return [None]
                
            if len(tree_cache[start][end]) > 0:
                return tree_cache[start][end]
            
            for root in xrange(start, end + 1):
                for l_subtree in self.gen_trees_util(start, root-1, tree_cache):
                    for r_subtree in self.gen_trees_util(root+1, end, tree_cache):
                        curr_root = TreeNode(root)
                        curr_root.left = l_subtree
                        curr_root.right = r_subtree
                        tree_cache[start][end].append(curr_root)
                        
            return tree_cache[start][end]
            
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n < 1:
                return []
                
            tree_cache = [[[] for j in xrange(n+1)] for i in xrange(n+1)]
            return self.gen_trees_util(1, n, tree_cache)

Log in to reply
 

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