本文最后更新于 2025-03-30T12:48:26+08:00
题目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| 给你一个整数 n ,求恰由 n 个节点组成且节点值
从 1 到 n 互不相同的 二叉搜索树 有多少种?
返回满足题意的二叉搜索树的种数。
示例 1:
输入:n = 3 输出:5 示例 2:
输入:n = 1 输出:1
提示:
1 <= n <= 19
|
题目思路
- 1、本题采用动态规划求解子问题,其中 dp[j - 1] 为左子树 j 个节点组成的二叉树种数,dp[i - j]为右子树 i - j 个节点组成的二叉树种数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public: int numTrees(int n) { vector<int> dp(n + 1, 0); dp[0] = dp[1] = 1; for(int i = 2; i <= n; i++) { for(int j = 1; j <= i; j++) { dp[i] += dp[j - 1] * dp[i - j]; } } return dp[n]; } };
|
复杂度
时间复杂度:O(nlogn)
空间复杂度:O(n)
Day 68 96. 不同的二叉搜索树
https://chaggle.github.io/2021/11/16/Leetcode/91-day/day-68/