Description
给定一个整数\(n\)，构造所有包含\([1,n]\)的二叉树。
Constraints
\(1 \le n \le 8\)
Solution
DFS即可。
Code
class Solution {
public:
vector<TreeNode*> generateTrees(int n) {
auto dfs = [&](auto &&dfs, int from, int to) -> vector<TreeNode*> {
vector<TreeNode*> ans;
for(int i = from; i <= to; ++i) {
auto lvec = dfs(dfs, from, i-1);
auto rvec = dfs(dfs, i+1, to);
for(auto l : lvec) for(auto r : rvec) {
ans.emplace_back(new TreeNode(i, l, r));
}
}
if(ans.empty()) ans.emplace_back(nullptr);
return ans;
};
return dfs(dfs, 1, n);
}
};