95. 不同的二叉搜索树 II

🟠   🔖  树 二叉搜索树 动态规划 回溯 二叉树  🔗 力扣 LeetCode

题目

Given an integer n, return _all the structurally unique **BST '**s (binary search trees), which has exactly _n nodes of unique values from 1 ton. Return the answer in any order.

Example 1:

Input: n = 3

Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

Input: n = 1

Output: [[1]]

Constraints:

• 1 <= n <= 8

题目大意

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

解题思路

这个问题可以使用递归来解决：

1. 定义一个辅助函数 helper，该函数接收两个参数 start 和 end，表示当前范围内可以使用的节点值的范围。
2. 如果 start 大于 end，说明当前范围为空，返回一个包含 null 的数组。
3. 遍历当前范围内的所有节点值（从 start 到 end），以当前节点值作为根节点，递归生成左子树和右子树。
4. 将左子树和右子树的所有可能组合连接到当前根节点，形成新的二叉搜索树。
5. 返回所有生成的二叉搜索树的根节点数组。

代码

/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
	if (n == 0) return [];
	const helper = (start, end) => {
		if (start > end) return [null];

		let res = [];
		for (let i = start; i <= end; i++) {
			const leftTrees = helper(start, i - 1);
			const rightTrees = helper(i + 1, end);

			for (let left of leftTrees) {
				for (let right of rightTrees) {
					res.push(new TreeNode(i, left, right));
				}
			}
		}
		return res;
	};
	return helper(1, n);
};

相关题目

题号	标题	题解	标签	难度
96	不同的二叉搜索树	[✓]	树 二叉搜索树 数学 2+
241	为运算表达式设计优先级		递归 记忆化搜索 数学 2+