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的所有可能性

解题思路：

DFS中比较难的catalan类型。

解题步骤：

N/A

注意事项：

1. root = TreeNode(i)要在最内层for循环中

Python代码：

def generateTrees(self, n: int) -> List[TreeNode]:
	return self.dfs(1, n)

def dfs(self, start, end):
	if start > end:
		return [None]
	if start == end:
		return [TreeNode(start)]
	res = []
	for i in range(start, end + 1):
		left_nodes = self.dfs(start, i - 1)
		right_nodes = self.dfs(i + 1, end)
		for _l in left_nodes:
			for _r in right_nodes:
				root = TreeNode(i)
				root.left = _l
				root.right = _r
				res.append(root)
	return res

算法分析：

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