题解42 | #不同的二叉搜索树(二)#

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return TreeNode类vector
     */
    vector<TreeNode*> dfs(int n, int start) {
        vector<TreeNode*> res;
        //0个的时候
        if (n < start) {
            res.push_back(nullptr);
            return res;
        }
        //1个的时候
        if (n == start) {
            TreeNode* node = new TreeNode(n);
            res.push_back(node);
            return res;
        }
        //开始以res里每一个点为根建立搜索树
        for (int i = start; i <= n; i++) {

            vector<TreeNode*> left = dfs(i-1, start);
            vector<TreeNode*> right = dfs(n, i+1);

            for (int j = 0; j < left.size(); j++) {
                for (int k = 0; k < right.size(); k++) {
                    TreeNode* temp = new TreeNode(i);
                    temp->left = left[j];
                    temp->right = right[k];
                    res.push_back(temp);
                }
            }
        }
        return res;
    }
    vector<TreeNode*> BSTgenerate(int n) {
        // write code here
        return dfs(n, 1);
    }

};

该算法的基本思想

通过递归的方式生成所有可能的二叉搜索树。对于每个根节点的值i，递归生成左子树和右子树，然后将左子树和右子树的所有可能组合起来，构造出以i为根节点的所有可能的二叉搜索树。

具体实现上，定义一个递归函数dfs，参数为n和start，表示生成以[start, n]范围内数字构成的二叉搜索树。首先判断如果n小于start，表示没有数字可以构成二叉搜索树，此时将nullptr加入结果中。然后判断如果n等于start，表示只有一个数字可以构成二叉搜索树，此时将以该数字为值的节点加入结果中。接下来，对于[start, n]范围内的每个数字i，递归生成以i为根节点的左子树和右子树，然后将左子树和右子树的所有可能组合起来，构造出以i为根节点的所有可能的二叉搜索树。

最后，调用dfs函数生成以1到n为节点值的所有可能的二叉搜索树。

时间复杂度为O(4^n/n^(3/2))，（1<=n<=10）

空间复杂度为O(4^n/n^(3/2))。（1<=n<=10）