生成所有不同的二叉搜索树 II - 算法与代码实现

不同的二叉搜索树 II（Unique Binary Search Trees II）是一个经典的算法问题，要求生成所有可能的二叉搜索树（BST），这些树由给定的 n 个节点组成，每个节点的值从 1 到 n 唯一。

问题描述

给定一个整数 n，生成所有由 1 到 n 组成的不同的二叉搜索树。

解决思路

这个问题可以通过递归和分治的思想来解决。对于每个可能的根节点，递归地生成左子树和右子树，然后将它们组合起来形成完整的二叉搜索树。

代码实现

以下是使用 JavaScript 实现的代码：

function generateTrees(n) {
    if (n === 0) return [];
    return generate(1, n);
}

function generate(start, end) {
    const result = [];
    if (start > end) {
        result.push(null);
        return result;
    }

    for (let i = start; i <= end; i++) {
        const leftTrees = generate(start, i - 1);
        const rightTrees = generate(i + 1, end);

        for (let left of leftTrees) {
            for (let right of rightTrees) {
                const root = new TreeNode(i);
                root.left = left;
                root.right = right;
                result.push(root);
            }
        }
    }

    return result;
}

class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

// 示例用法
const trees = generateTrees(3);
console.log(trees);

代码解释

1. generateTrees(n): 这是主函数，调用 generate(1, n) 来生成所有可能的二叉搜索树。
2. generate(start, end): 这是一个递归函数，用于生成从 start 到 end 的所有可能的二叉搜索树。
   • 如果 start > end，说明当前子树为空，返回 [null]。
   • 对于每个可能的根节点 i，递归生成左子树和右子树。
   • 将左子树和右子树的所有组合与当前根节点组合起来，形成完整的二叉搜索树，并添加到结果数组中。
3. TreeNode: 这是一个简单的二叉树节点类，用于构建二叉搜索树。

示例输出

对于 n = 3，生成的二叉搜索树如下：

[
  TreeNode {
    val: 1,
    left: null,
    right: TreeNode {
      val: 2,
      left: null,
      right: TreeNode { val: 3, left: null, right: null }
    }
  },
  TreeNode {
    val: 1,
    left: null,
    right: TreeNode {
      val: 3,
      left: TreeNode { val: 2, left: null, right: null },
      right: null
    }
  },
  TreeNode {
    val: 2,
    left: TreeNode { val: 1, left: null, right: null },
    right: TreeNode { val: 3, left: null, right: null }
  },
  TreeNode {
    val: 3,
    left: TreeNode {
      val: 1,
      left: null,
      right: TreeNode { val: 2, left: null, right: null }
    },
    right: null
  },
  TreeNode {
    val: 3,
    left: TreeNode {
      val: 2,
      left: TreeNode { val: 1, left: null, right: null },
      right: null
    },
    right: null
  }
]

复杂度分析

• 时间复杂度: O(C_n)，其中 C_n 是第 n 个卡特兰数，表示所有可能的二叉搜索树的数量。
• 空间复杂度: O(C_n)，用于存储所有可能的二叉搜索树。

这个算法通过递归和分治的思想，有效地生成了所有可能的二叉搜索树，适用于中等规模的 n。