96. Unique Binary Search Trees

淡淡的烟草味﹌ 2024-04-07 11:53 194阅读 0赞

Given an integer n, return the number of structurally unique BST’s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

9d5e5b463ee27c06dac2aa90c957e636.jpeg

  1. Input: n = 3
  2. Output: 5

Example 2:

  1. Input: n = 1
  2. Output: 1

Constraints:

  • 1 <= n <= 19

题目：给一个正整数n,求由节点1~n组成的二叉搜索树结构有几个

思路：由于是二叉搜索树，因此只要根节点确定了，左右子树节点个数也就确定。从1到n遍历，分别从1到n作为根节点，求左右子树的结构个数相乘。最后的加和即为结果。为减少重复运算，用vector数组dp记录i个节点的结构数。代码：

  1. class Solution {
  2. private:
  3.     vector<int> dp;
  4. public:
  5.     int helper(int n){
  6.         if(dp[n] > 0) return dp[n];
  7.         for(int i = 0; i<n; i++){
  8.             dp[n] += helper(i) * helper(n-i-1);
  9.         }
  10.         return dp[n];
  11.     }
  12.     int numTrees(int n) {
  13.         dp.resize(n+1, 0);
  14.         dp[0] = 1;
  15.         return helper(n);
  16.     }
  17. };

发表评论

表情：
评论列表 （有 0 条评论，194人围观）

还没有评论，来说两句吧...

相关阅读