Leetcode 95. 不同的二叉搜索树 II

题目

Leetcode 95. 不同的二叉搜索树 II

代码（9.21 首刷看解析）

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return build(1,n);
    }
    vector<TreeNode*> build(int l, int r) {
        vector<TreeNode*> res;
        if(l > r) {
            res.emplace_back(nullptr);
            return res;
        }
        for(int i = l; i <= r; i++) {
            auto leftTree = build(l, i-1);
            auto rightTree = build(i+1, r);
            for(auto left : leftTree) {
                for(auto right : rightTree) {
                    auto root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.emplace_back(root);
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

代码（10.7 二刷看解析）

class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        return build(1, n);
    }
    vector<TreeNode*> build(int l, int r) {
        if(l > r)
            return {nullptr};
        vector<TreeNode*> res;
        for(int i = l; i <= r; i++) {
            auto leftTree = build(l, i-1);
            auto rightTree = build(i+1, r);
            for(auto& left : leftTree) {
                for(auto& right : rightTree) {
                    auto root = new TreeNode(i);
                    root->left = left;
                    root->right = right;
                    res.emplace_back(root);
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24