95. 不同的二叉搜索树 II

题目

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

示例 1：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
示例 2：

输入：n = 1
输出：[[1]]

提示：

1 <= n <= 8

链接

95. 不同的二叉搜索树 II

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n) return {};
        return dfs(1, n);
    }

    vector<TreeNode*> dfs(int l, int r){
        vector<TreeNode*> res;
        if(l > r){
            res.push_back(NULL);
            return res;   
        }

//l = 1, r = r
// k=1 -> (1~0)*(2~r) + 
// k=2 -> (1~1)*(3~r) + 
// k=3 -> (1~2)*(4~r) + ... + 
// k=r -> (1~r-1)*(r+1~r)       
        for(int k = l; k <= r; k++){             
            vector<TreeNode*> left = dfs(l, k-1);                                                 
            vector<TreeNode*> right = dfs(k+1, r);
            for(TreeNode* i : left)//枚举l~k-1组成的所有左子树情况，即左子树集合
                for(TreeNode* j : right){//枚举k+1~r组成的所有右子树情况，即右子树集合
                    auto root = new TreeNode(k);//创建节点k
                    root->left = i, root->right = j;//以k为根节点，拼接二叉搜索树
                    res.push_back(root);//把当前的二叉搜索树放入l~r集合中
                } 
        }
        return res;//返回以l~r为节点的二叉搜索树的所有情况
    }
};
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43