[BackTracking]95. Unique Binary

• 分类：BackTracking
• 时间复杂度: O(?)
• 空间复杂度: O(?)

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

代码：

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

class Solution:
    def generateTrees(self, n: 'int') -> 'List[TreeNode]':
        
        if n<1:
            return []
        
        res=self.helper(1,n)
        return res
    
    def helper(self,start,end):
        
        if (start>end):
            return [None]
        
        if (start==end):
            return [TreeNode(start)]
        
        res=[]
        for i in range(start,end+1):
            left=self.helper(start,i-1)
            right=self.helper(i+1,end) 
#           不能把current=TreeNode(i)放在这个地方是因为存在list中的current可能还是同一个current
            for l in left:
                for r in right:
                    current=TreeNode(i)
                    current.left=l
                    current.right=r
                    res.append(current)
        return res

讨论：

1.不能把current=TreeNode(i)放在我打注释的那个地方是因为存在list中的current可能还是同一个current，所以这样写看似方便了，其实有问题