leetcode95. 不同的二叉搜索树 II

分析

我们定义 generateTrees(start, end) 函数表示当前值的集合为 [start,end]，返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举[start,end] 中的值 ii 为当前二叉搜索树的根，那么序列划分为了 [start,i−1] 和[i+1,end] 两部分。我们递归调用这两部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。
递归的入口即为 generateTrees(1, n)，出口为当 start>end 的时候，当前二叉搜索树为空，返回空节点即可。-----leetcode官解

/**
 * 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 start,int end){
        if(start>end)return {nullptr};//出口
        vector<TreeNode*> ans;
        for(int i=start;i<=end;i++){
            vector<TreeNode*> left=generateTrees(start,i-1);//生成比i小的左子树
            vector<TreeNode*>right=generateTrees(i+1,end);//生成比i大的左子树
            for(auto l:left){//从所有左右子树中选一个作为i的左右子树
                for(auto r:right){
                    TreeNode* cur=new TreeNode(i);
                    cur->left=l;
                    cur->right=r;
                    ans.push_back(cur);
                }
            }
        }
        return ans;
    }
    vector<TreeNode*> generateTrees(int n) {
        if(!n)return{};
        return generateTrees(1,n);
    }
};