95.不同的二叉搜索树 II

两天宇宙人

2020-01-21

🥧递归

写递归最重要的点在于：
不要在乎递归是如何运行的，你要在乎的是，通过设计什么样的递归公式，递归出口，就一定可以通过递归获得最终的值。而不是去考虑递归在计算机中以什么样的形式和流程去执行的。

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n)
            return vector<TreeNode*>();
        return helper(1, n);
    }

    vector<TreeNode*> helper(int start, int end) {
        vector<TreeNode*> ret;
        if(start > end) {
            ret.push_back(nullptr);
            return ret;
        }
        for(int i = start; i <= end; ++i)
        {
            auto leftList = helper(start, i - 1);
            auto rightList = helper(i + 1, end);
            for(auto l : leftList) 
                for(auto r: rightList) 
                {
                    auto newOne = new TreeNode(i);
                    newOne->left = l;
                    newOne->right = r;
                    ret.push_back(newOne);
                }
        }
        return ret;
    }
};