From
Leetcode
Status
回头复习下
Date
Apr 9, 2024
Tags
二叉搜索树
动态规划
Difficulty
中等
题面
给你一个整数
n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。示例 1:
![notion image](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg?t=f7a667ec-e7c7-4cfc-801b-74d071bbd4cb)
示例 2:
提示:
1 <= n <= 19
思路
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2F13d5f67b-84ef-4697-92f8-fac38e183453%2Fd87fef19-02ec-4209-9a52-76a1a57f22ef%2FUntitled.png?table=block&id=add6c02e-9ca3-4358-a0f8-39ae456c1210&t=add6c02e-9ca3-4358-a0f8-39ae456c1210&width=2016&cache=v2)
dp[3],就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量