【Leetcode】96. Unique Binary Search Trees

绝地灬酷狼 2022-02-20 11:23 285阅读 0赞

Given n, how many structurally unique BST’s(binary search trees) that store values 1 … n?

Example:

  1. Input: 3
  2. Output: 5
  3. Explanation:
  4. Given n = 3, there are a total of 5 unique BST's:
  6.    1         3     3      2      1
  7.     \       /     /      / \      \
  8.      3     2     1      1   3      2
  9.     /     /       \                 \
  10.    2     1         2                 3

题目大意：

不使用链表，求解1…n可以组成多少个BST（二叉搜索树）。

解题思路：

1…n中每个节点都当作根节点，左右两边分别为先前已得到的结果，左右两边的个数相乘。保存当前位置的结果。

faster than 100%

  1. class Solution {
  3. public:
  4.     int numTrees(int n) {
  5.         vector<int> ans;
  6.         ans.push_back(1);
  7.         for(int i = 1;i<=n;i++){
  8.             int start = 1, end = i;
  9.             int tmp = 0;
  10.             for(int j = 1;j<=i;j++){
  11.                 int l = j-start;
  12.                 int r = end - j;
  13.                 tmp += (ans[l]*ans[r]);
  14.             }
  15.             ans.push_back(tmp);
  16.         }
  17.         return ans[n];
  18.     }
  19. };

发表评论

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

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

相关阅读