96. 不同的二叉搜索树

🟠   🔖  树 二叉搜索树 数学 动态规划 二叉树  🔗 力扣 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 1to n.

Example 1:

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);
};

相关题目

题号	标题	题解	标签	难度
95	不同的二叉搜索树 II	[✓]	树 二叉搜索树 动态规划 2+