【leetcode系列】【算法】【中等】不同的二叉搜索树 II(卡特兰数问题))

本文主要是介绍【leetcode系列】【算法】【中等】不同的二叉搜索树 II(卡特兰数问题))，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

题目链接： https://leetcode-cn.com/problems/unique-binary-search-trees-ii/

解题思路：

如果只是求个数，可直接通过卡特兰数递推公式求解：

假设 $C_{n + 1}$ 是卡特兰数的第n + 1项，则：

$C_{n + 1} = C_{0}C_{n} + C_{1}C_{n - 1} + ... + C_{n}C_{0} = \sum _{i = 0}^{n}C_{i}C_{n - i} = \frac {2(2n + 1)}{n + 2}C_{n}\approx \frac {4^{n}}{n^{\frac {2}{3}}\sqrt{\pi }}$

其中， $C_{0} = 1, C_{1} = 1$

其他常见的符合卡特兰数递推公式的例子有：括号化、出栈次序、凸多边形三角划分、n对括号正确匹配数目

所以如果不需要列出所有的例子，只需要从0开始递推，就可以求出任意项的卡特兰数

但是此处需要列出所有例子，所以没办法使用此方法，需要使用递归的方式，遍历所有的可能性

递归时候的思路为：

选定一个数，作为当前节点值
使用小于当前值的数字递归调用自己，创建左子树
使用大于当前值的数字递归调用自己，创建右子树
向后移动一位作为当前节点值，继续重复循环

代码实现：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = Noneclass Solution:def generateTrees(self, n: int) -> List[TreeNode]:def create_res(start, end):# 如果start > end,说明以及到了叶子节点,直接返回Noneif start > end:return [None,]res = []for i in range(start, end + 1):# 创建左子树left_trees = create_res(start, i - 1)# 创建右子树right_trees = create_res(i + 1, end)for left in left_trees:for right in right_trees:# 如果是叶子节点,left和right都为None# 之后再向上递归,逐渐创建一系列完整的树node = TreeNode(i)node.left = leftnode.right = rightres.append(node)return resif 0 == n:return []return create_res(1, n)

这篇关于【leetcode系列】【算法】【中等】不同的二叉搜索树 II(卡特兰数问题))的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！