Leetcode_95_不同的二叉搜索树Ⅱ_hn
2020-03-19 本文已影响0人
1只特立独行的猪
题目描述
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例
示例 1：
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
解答方法
方法一：
思路
- 1.利用卡特兰数求解，G(n) = ∑i∈[0,n] G(i)G(n-i-1)
- 2.主要通过切点i,判断i的左右是否存在构成新的节点条件的值。
- 2.1 对于左边：是否存在x满足start<=x<i的值，如果存在则递归继续切分，继续判断，知道不满足返回[None]。
- 2.2 对于右边：是否存在x满足i<x<=end的值，如果存在则递归继续切分，继续判断，直到不满足返回[None]]。
- 3.通过for循环其实有着计算是个笛卡尔积的作用，leftright种可能。在循环中依次生成新的节点可能性，添加到all_trees列表中，
最后输出的列表将会包含所有中可能。因为该动态规划，采用自顶而下的方式。
注：这里用列表存储，因为继续切分得到的结果可能有多个，为了将这些结果合并，需采用for循环。
https://leetcode-cn.com/problems/unique-binary-search-trees-ii/solution/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode/
代码
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
def generate_tree(start, end):
if start>end:
return [None]
all_trees = []
for i in range(start,end+1):
left_trees = generate_tree(start, i-1)
right_trees = generate_tree(i+1, end)
for l in left_trees:
for r in right_trees:
current_tree = TreeNode(i)
current_tree.left = l
current_tree.right = r
all_trees.append(current_tree)
return all_trees
if n:
return generate_tree(1,n)
else:
return []
