LeetCode 095 Unique Binary Search Trees II

LeetCode

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1
Output: [[1]]

Constraints:

* 1 <= n <= 8

题目大意：

给定n，求所有val为1-n的BST的所有可能性,返回结果是所有可能的root的集合。

解题思路：

DFS中比较难的catalan类型。

解题步骤：

N/A

注意事项：

1. root = TreeNode(i)要在最内层for循环中
2. 返回结果是解的集合，所以终止条件返回也需要是一个[None]

Python代码：

# catelan dfs (type 4) LeetCode 095 Unique Binary Search Trees II
# return the root of all the possible trees
def generateTrees(self, n: int) -> List[TreeNode]:
	nums = [_ + 1 for _ in range(n)]
	return self.dfs4(nums, 0, n)

def dfs4(self, nums, start, end): # [start, end)
	if start >= end:
		return [None] # remember becaues we want the 2 for-loop happen
	res = []
	for i in range(start, end):
		left_root_nodes = self.dfs4(nums, start, i) # 0, 0
		right_root_nodes = self.dfs4(nums, i + 1, end) # 1, 1
		for left_root_node in left_root_nodes:
			for right_root_node in right_root_nodes:
				node = TreeNode(nums[i])
				node.left = left_root_node
				node.right = right_root_node
				res.append(node)
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)