Leetcode_96. 不同的二叉搜索树
96. 不同的二叉搜索树
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
示例 1:
1 | **输入:**n = 3 |
示例 2:
1 | **输入:**n = 1 |
提示:
1 <= n <= 19
解析
观察这些树的结构,发现每一个节点都可以作为根节点,由于是排序树,
对于根节点i
,左子树将有i-1
个节点,右子树将有n-i
个节点((i-1)+1+(n-i))=n。所以对于n个节点,每个节点轮流做根节点,然后再分别计算其左右子树组合的可能性,最后再累加再一起就是总个数。这种策略是我们可以很容易分割问题规模,自底向上的重复使用已有的结果。
定义
dp[i]
表示n
个节点组成且节点值从1
到n
互不相同的 二叉搜索树 的个数。
初始化
1 | dp[1]=1; |
递推方程
实现
1 | class Solution { |
评论