题解 | 不同的二叉搜索树

题干分析:

题目要求我们生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。

二叉搜索树定义如下：

• 节点的左子树只包含 严格小于 当前节点的数。
• 节点的右子树只包含 严格大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

算法逻辑:

针对编码为1~n,根节点编码为i的二叉搜索树可以看作左子树编码为1~(i-1)的二叉搜索树与右子树为(i+1)~n编码的二叉树拼在编码为i的根节点形成,因此我们通过引入构建编码为start~end的所有二叉搜索树辅助函数进构建,每次循环从i=start到i=end每次循环进行笛卡尔组合所有可能的左右子树.

实现代码:

class L95 {
    vector<TreeNode *> generateBST(int start, int end) {
        vector<TreeNode *> ret;

        if (start > end) { // 搜索树不存在则压入空并返回
            ret.push_back(nullptr);
            return ret;
        }

        for (int i = start; i <= end; ++i) {
            // 获取左右子树
            vector<TreeNode *> leftTree = generateBST(start, i - 1);
            vector<TreeNode *> rightTree = generateBST(i + 1, end);

            // 合并
            for (auto LT: leftTree) {
                for (auto RT: rightTree) {
                    auto root = new TreeNode(i, LT, RT);
                    ret.push_back(root);
                }
            }
        }

        return std::move(ret); // 移动语义,减少拷贝消耗
    }

public:
    vector<TreeNode *> generateTrees(int n) {
        return generateBST(1, n);
    }
};

复杂度分析:

该算法时间与空间复杂度均取决于卡兰特数的大小.

关于卡兰特数C(n):

设T(n)为生成n个节点的BST所需时间,则:

这恰好是卡特兰数的递推关系,因此时间复杂度为O(C(n))

针对空间复杂度,由于树的个数即为卡兰特数,每个树节点消耗O(n)的空间,因此空间复杂度为O(nC(n))