算法思路

一般关于二叉树的问题都可以用递归来解决， 同时二叉搜索树又是一种根据递归定义的树，所以此题可由递归来求解。

读于一棵二叉搜索树来说，一个重要的性质就是它的中序遍历为升序，中序遍历的过程为左 -> 根 -> 右，如果给每个结点标记上编号，意思就是说所有左子树节点的编号一定小于根节点，所有右子树的结点编号大于根节点。在此题中给定了一个中序遍历顺序1 ~ n， 于是我们的思路如下：

1. 先枚举根节点的位置，将问题划分为分别递归求解左边子树和右边子树
2. 递归返回的是所有合法方案的集合，所以枚举每种合法的左右儿子
3. 枚举左右儿子和根节点作为一种合法方案记录下来

C ++代码

/**
 * 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) return {};
        return dfs(1, n); 
    }

    vector<TreeNode*> dfs(int l, int r) //返回在区间[l, r]中所有合法方案
    {
        vector<TreeNode*> res;
        if (l > r) 
        {
            res.push_back(nullptr); 结点为空，是一种子树的方案，需要加入方案集中
            return res;
        }

        for (int i = l; i <= r; i ++) //枚举根节点位置
        {
            auto left = dfs(l, i - 1); //返回左子树所有合法方案
            auto right = dfs(i + 1, r); //返回右子树所有合法方案

            for (auto &lt : left) //一个左子树
                for (auto &rt : right) //一个右子树
                {
                    TreeNode* root = new TreeNode(i); //创建根节点
                    root -> left = lt;
                    root -> right = rt;
                    res.push_back(root); //加入以该结点为根的合法方案
                }
        }

        return res;
    }
};