95. Unique Binary Search Trees 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. 不同的二叉搜索树
• 241. 为运算表达式设计优先级

- [96. 不同的二叉搜索树](./0096.md)
- [241. 为运算表达式设计优先级](https://leetcode.com/problems/different-ways-to-add-parentheses)