全部查找树

要求

输出所有由数字1~n 组成的二叉搜索树。

eg:

n = 2

answer: 1(,2), 2(1)

解决思路

我们先从所有数字中取出一个作为根节点，那么剩下的数字按大小划分刚好能各自形成一棵二叉树（没有数字的那半用空指针代替）。因此，我们可以用相同的方式产生该根节点的子树的所有情况，最后把左子树和右子树的情况组合起来，每一种组合都是一棵新树，这样，在遍历完根节点的所有情况之后，就可以得到答案。

vector<Node*> BuildTrees(int s, int e){
    //如果没有可以形成二叉树的数字，则返回空结点
    if(s > e)return vector<Node*>(1, NULL);
    
    vector<Node*> trees;
    //遍历每一个根节点
    for(int i = s; i <= e; i++){
        vector<Node*> left_trees = BuildTrees(s, i - 1); //所有左子树的情况
        vector<Node*> right_trees = BuildTrees(i + 1, e);//所有右子树的情况
        //将每个左右子树组合起来形成一棵新的二叉树
        for(int j = 0; j < left_trees.size(); j++){
            for(int k = 0; k < right_trees.size(); k++){
                Node *root = new Node(i, NULL, NULL);
                root->left = left_trees[j];
                root->right = right_trees[k];
                trees.push_back(root);
            }
        }
    }
    return trees;
}

vector<Node*> solution(int n){
    return BuildTrees(1, n);
}
C++