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);
    }
};

LeetCode-95 Unique Binary Search Trees II