0095._Unique_Binary_Search_Trees_II.md

95. Unique Binary Search Trees II

难度: Medium

刷题内容

原题连接

• 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.

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

解题方案

思路 1 - 时间复杂度: O(4^ N / sqrt(N))- 空间复杂度: O(4^ N / sqrt(N))******

因为知道这是一棵二叉搜索树，所以left.val < root.val < right.val

然后可以任意取一个node作为root，递归调用左边用返回的node作为left，递归调用右边用返回的node作为right

注意考虑n为0的情况，应该返回[]而不是[[]]

beats 75.00%

class Solution:
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n == 0:
            return []
        
        def helper(nums):
            if not nums:
                return [None]
            res = []
            for idx, num in enumerate(nums):
                for l in helper(nums[:idx]):
                    for r in helper(nums[idx+1:]):
                        node = TreeNode(num)
                        node.left = l
                        node.right = r
                        res.append(node)
            return res
        
        return helper(list(range(1, n+1)))