Python solution with detailed explanation


  • 0
    G

    Solution

    Unique Binary Search Trees II https://leetcode.com/problems/unique-binary-search-trees-ii/

    Dynamic Programming Approach

    • The number of different roots can range from 1 to i
    • We do not need to change left subtree. But right subtree vals has to be shifted.
    • Take i = 10 and j = 6. Left subtree [1,5] and right subtree [7-10].
    • Right subtree has 4 nodes and all the trees in it will be structurally similar to trees with [1-4] nodes.
    • So we simply need to copy each tree for [1-4] and shift its value by offset.
    • Copy tree will use a tree traversal like pre-order.
    • In this problem even if we use dp, we should copy the cached result each time we use it instead of the cached result itself. So we won't actually save time.

    Recursive Approach:

    • In this problem even if we use dp, we should copy the cached result each time we use it instead of the cached result itself. So we won't actually save time.
    class Solution(object):
        def helper(self, start, end):
            result = []        
            if start > end:
                result.append(None)
            else:
                for root in range(start, end+1):
                    left, right = self.helper(start, root-1), self.helper(root+1, end)
                    for lt in left:
                        for rt in right:
                            x = TreeNode(root)
                            x.left, x.right = lt, rt
                            result.append(x)
            return result
        
        def generateTrees(self, n):
            """
            :type n: int
            :rtype: List[TreeNode]
            """
            if n == 0:
                return []
            return self.helper(1, n)
    

Log in to reply
 

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