96. Unique Binary Search Trees
96. Unique Binary Search Trees
🟠 🔖 树
二叉搜索树
数学
动态规划
二叉树
🔗 LeetCode
题目
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:
![](https://assets.leetcode.com/uploads/2021/01/18/uniquebstn3.jpg)
Input: n = 3
Output: 5
Example 2:
Input: n = 1
Output: 1
Constraints:
1 <= n <= 19
题目大意
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
解题思路
可以使用递归 + 记忆化的方法。
递归的思路是,对于每个节点 i
(1 <= i <= n
),将其作为根节点,然后计算左子树有 i-1
个节点的 BST 数量,以及右子树有 n-i
个节点的 BST 数量。最后将左右子树的数量相乘,即可得到以节点 i
为根节点的 BST 数量。
但是这种递归的方法在计算中会有很多重复的子问题,因此效率较低,尤其是在 n
较大的情况下。可以通过添加一个缓存(字典)来存储已计算的中间结果,以便在需要时直接返回而不进行重复计算,这个过程通常称为"记忆化"。
var numTrees = function (n) {
const memo = {};
const helper = (n) => {
if (n === 0 || n === 1) {
return 1;
}
if (memo[n] !== undefined) {
return memo[n];
}
let total = 0;
for (let i = 1; i <= n; i++) {
total += helper(i - 1) * helper(n - i);
}
memo[n] = total;
return total;
};
return helper(n);
};
// 示例用法
console.log(numTrees(3)); // 输出: 5
console.log(numTrees(1)); // 输出: 1
在这个例子中,memo
是一个对象,用于存储已计算的结果。在递归函数中,首先检查 memo
中是否已经有了对应 n
的计算结果,如果有就直接返回,否则进行计算并将结果存入 memo
中。这样可以显著减少递归中的重复计算,提高效率。
代码
/**
* @param {number} n
* @return {number}
*/
var numTrees = function (n) {
let memo = new Map();
const helper = (n) => {
if (n <= 1) return 1;
if (memo.has(n)) return memo.get(n);
let total = 0;
for (let i = 1; i <= n; i++) {
total += helper(i - 1) * helper(n - i);
}
memo.set(n, total);
return total;
};
return helper(n);
};