95. Unique Binary Search Trees II (Tree; DFS)

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> result;
        if(n==0)
        {
            result.push_back(NULL);
            return result;
        }
        recursion(1,n, result);
        return result;
    }
    
    void recursion(int start, int end, vector<TreeNode*> &root)
    {
        if(start == end) //递归结束条件：只剩一个节点
        {
            root.push_back(new TreeNode(start)); //新建节点返回
            return;
        }
        
        for(int i = start; i<=end; i++) 
        {   
            vector<TreeNode*> leftTree;
            vector<TreeNode*> rightTree;
            if(i > start) 
            {
                recursion(start, i-1, leftTree); //i-1,所以至少去掉了一种情况
            }
            if(i < end)
            {
                recursion(i+1, end, rightTree); //i+1,同理至少去掉了一种情况
            }
            if(leftTree.empty())
            {
                for(int j = 0; j< rightTree.size(); j++)
                {
                    TreeNode* newRoot = new TreeNode(i); //新建节点
                    newRoot->right = rightTree[j];
                    root.push_back(newRoot);
                 }
            }
            else if(rightTree.empty())
            {
                 for(int j = 0; j< leftTree.size(); j++)
                 {
                     TreeNode* newRoot = new TreeNode(i); 
                     newRoot->left = leftTree[j];
                     root.push_back(newRoot);
                 }
            }
            else{
                 for(int j = 0; j< leftTree.size(); j++)
                 {
                     for(int k = 0; k< rightTree.size(); k++)
                     {
                         TreeNode* newRoot = new TreeNode(i);
                         newRoot->left = leftTree[j];
                         newRoot->right = rightTree[k];
                         root.push_back(newRoot);
                     }
                 }
            }
        }  
    }
};