题目内容

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

示例

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

示例 2：

输入：n = 1
输出：[[1]]

提示

1 <= n <= 8

题解

本题采用深度优先搜索算法求解。在思考上，本题通过枚举根节点的位置来依次生成二叉搜索树。思考如下：

1、对于每段连续的序列[L,R]枚举二叉搜索树根节点的位置
2、分别递归求出[L,K-1],[K+1,R]的所有子树方案；
3、将左子树的任意一种方案和右子树的任意一种方案拼在一起，就可以得到当前节点的一种方案

在编程实现上，每次根节点需要重新new出来，因为如果只用1个根节点，其实最后放入res中的答案全部一样，就错了！从计算机本身的原理上来说，是针对相同的内存地址修改其值。

注：本题中N个节点的二叉搜索树方案数为卡特兰数，公式为：

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n==0) return {};
        return dfs(1,n);
    }

    vector<TreeNode*> dfs(int l,int r){
        //当前子区间内一个点都没有，就返回空
        if(l>r) return {NULL};
        vector<TreeNode*> res;
        for(int i = l; i <= r; i++){
            auto left = dfs(l,i-1);
            auto right = dfs(i+1,r);
            for(auto l:left)
                for(auto r:right){
                    auto root = new TreeNode(i);
                    root->left = l;
                    root->right = r;
                    res.push_back(root);
                }
        }
        return res;
    }
};