leetcode 95 不同的二叉搜索树 Ⅱ

原题传送门—>>

题目描述：

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

示例:

-输入：3
-输出：
-[

• [1,null,3,2],
• [3,2,null,1],
• [3,1,null,null,2],
• [2,1,3],
• [1,null,2,null,3]
  -]
  -解释：
  -以上的输出对应以下 5 种不同结构的二叉搜索树：
  -
• 1 3 3 2 1
• \ / / / \ \
• 3 2 1 1 3 2
• / / \ \
• 2 1 2 3

提示：

0 <= n <= 8

这里采用的是官方思路

class Solution {
public:
    vector<TreeNode*> generateTrees(int left, int right)
    {
        vector<TreeNode *> ans;
        if(left > right)
        {
            ans.push_back(NULL);
            return ans;
        }//注意这里push NULL !!  因为左右子树都有可能是空指针
        vector<TreeNode*> leftTrees;
        vector<TreeNode*> rightTrees;
        for(int i = left; i <= right; ++i)
        {
            leftTrees = generateTrees(left, i-1);
            rightTrees = generateTrees(i + 1, right);
            for(int j = 0; j < leftTrees.size(); ++j)
            {
                for(int k = 0; k < rightTrees.size(); ++k)
                {
                    TreeNode * root = new TreeNode(i);
                    root -> left = leftTrees[j];
                    root -> right = rightTrees[k];
                    ans.push_back(root);
                }
            }
        }
        return ans;
    }

    vector<TreeNode*> generateTrees(int n) {
        if(n < 1)
            return vector<TreeNode*>();
        vector<TreeNode *> ans = generateTrees(1, n);
        return ans;
    }
};