95. Unique Binary Search Trees I

95. Unique Binary Search Trees II

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

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

First

对于此道题目而且，最重要是缓存递归当中重复递归的值。

由n个节点构建BST的所有可能性，等于1-n分别充当根节点构建BST节点的总和。

因此，可以求n个节点构建BST拆分成对应以k(1 <= k <= n)为根节点，查找1·k-1为左子树，k+1·n为右子树的所有可能BST
再将1·k-1的所有可能子树当k的左子树，k+1·n为k的右子树。这样就将大问题1·n的BST拆分成小问题（1·k-1, K+1·n的BST）

再求子树之后，将其所有可能的子书缓存起来，可以避免重复计算。

from quixote.structs.tree import TreeNode

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        def recursion(i, j, cache):
            if (i, j) in cache:
                return cache[(i, j)]
            if i == j:
                node = TreeNode(i)
                cache[(i, j)] = [node]
                return cache[(i, j)]
            if i > j:
                return [None,]
            tmp = []
            for k in range(i, j+1):
                left = recursion(i, k-1, cache)
                right = recursion(k+1, j, cache)
                for left_root in left:
                    for right_root in right:
                        k_node = TreeNode(k)
                        k_node.left = left_root
                        k_node.right = right_root
                        tmp.append(k_node)
            cache[(i, j)] = tmp
            return tmp

        return recursion(1, n, {})

s = Solution()
print(len(s.generateTrees(5)))