95.md

# 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]
        """
        ans = [[] for i in range(n+1)]
        ans[0] = [None]
        for op in range(1, n+1):
            for i in range(op):
                for left in ans[i]:
                    for right in ans[op-1-i]:
                        newTree = TreeNode(i+1)
                        newTree.left = self.copyTree(left)
                        newTree.right = self.copyTree(right)
                        self.addTree(newTree.right, i+1)
                        ans[op].append(newTree)
        if n == 0:
            return []
        return ans[n]
        
    def addTree(self, node, k):
        if node != None:
            node.val += k
            self.addTree(node.left, k)
            self.addTree(node.right, k)
            
    def copyTree(self, node):
        if node == None:
            return None
        else:
            newTree = TreeNode(node.val)
            newTree.left = self.copyTree(node.left)
            newTree.right = self.copyTree(node.right)
            return newTree

二叉树、记忆化搜索、递归