LeetCode-Unique Binary Search Trees I & II

96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
           /     /      /       
     3     2     1      1   3      2
    /     /                        
   2     1         2                 3

Solution

explanation: https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0 for i in range(n+1)]
        G[0] = G[1] = 1
        for i in range(2,n+1):
            for j in range(1,i+1):
                G[i] += G[i-j]*G[j-1]
        return G[n]

95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        return self.generateSubTrees(1, n)
    
    def generateSubTrees(self, s, e):
        res = []
        if s > e:
            res.append(None)
            return res
        for i in range(s,e+1):
            left = self.generateSubTrees(s,i-1)
            right = self.generateSubTrees(i+1,e)
            for lnode in left:
                for rnode in right:
                    root = TreeNode(i)
                    root.left = lnode
                    root.right = rnode
                    res.append(root)
                    
        return res