leetcode 96 不同的二叉搜索树

川长思鸟来 2022-09-16 06:22 286阅读 0赞

前言

题目：96. 不同的二叉搜索树

参考题解：不同的二叉搜索树-代码随想录

提交代码

这道题目没有想出来，看题解之后，自行写了一遍。

核心思想：[1,n]中选取一个值i。i将原区间分成左右子树[1,i-1],[i+1,n]。以i为根节点的二叉搜索树的种数，为左右子树种数的乘积。分别以[1,n]中每个节点为根，进行求和累计。

代码实现如下。

  1. class Solution {
  2. public:
  3.     int numTrees(int n) {
  4.         vector<int> dp(n+1,0);
  5.         dp[0] = 1;
  6.         for(int val=1; val<=n; val++){
  7.             for(int i=0; i<val; i++){ // 根据i，将val划分成左右两边。
  8.                 dp[val] += dp[i]*dp[val-1-i]; // 两边形状的排列组合，进行累加
  9.             }
  10.             // cout<<dp[val]<<" ";
  11.         }
  12.         return dp[n];
  13.     }
  14. };

发表评论

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

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

相关阅读