C++刷leetcode（95. 不同的二叉搜索树 II）【递归】

糖逗

题目描述：

1. 
   
2. 给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
   
3. 
   
4. 示例:
   
5. 
   
6. 输入: 3
   
7. 输出:
   
8. [
   
9.   [1,null,3,2],
   
10.   [3,2,null,1],
    
11.   [3,1,null,null,2],
    
12.   [2,1,3],
    
13.   [1,null,2,null,3]
    
14. ]
    
15. 解释:
    
16. 以上的输出对应以下 5 种不同结构的二叉搜索树：
    
17. 
    
18.    1         3     3      2      1
    
19.     \       /     /      / \      \
    
20.      3     2     1      1   3      2
    
21.     /     /       \                 \
    
22.    2     1         2                 3

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * struct TreeNode {
   
4. *     int val;
   
5. *     TreeNode *left;
   
6. *     TreeNode *right;
   
7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
   
8. * };
   
9. */
   
10. class Solution {
    
11. public:
    
12.     vector<TreeNode*> dfs(int start, int end){
    
13.         vector<TreeNode*> res;
    
14.         if(start > end){
    
15.             res.push_back(NULL);
    
16.             return res;
    
17.         }
    
18.         else if(start == end){
    
19.             TreeNode* root = new TreeNode(start);
    
20.             res.push_back(root);
    
21.             return res ;
    
22.         }
    
23.         else{
    
24.             for(int i = start; i <= end; i++){
    
25.                 vector<TreeNode*> left = dfs(start, i-1);
    
26.                 vector<TreeNode*> right = dfs(i+1, end);
    
27.                 for(auto ch1 : left){
    
28.                     for(auto ch2: right){
    
29.                         TreeNode*root = new TreeNode(i);
    
30.                         root -> left = ch1;
    
31.                         root -> right = ch2;
    
32.                         res.push_back(root);
    
33.                     }
    
34.                 }
    
35.             }
    
36.         }
    
37.         return res;
    
38.     }
    
39.     vector<TreeNode*> generateTrees(int n) {
    
40.         if(n == 0){
    
41.             vector<TreeNode*> res;
    
42.             return res;
    
43.         }
    
44.         else return dfs(1, n);
    
45.     }
    
46. };

复制代码

参考链接：https://leetcode-cn.com/problems ... -duo-jie-fa-by-2-7/

糖逗

需要再刷一下，没写出来

永恒的蓝色梦想

一直搞不懂二叉树……

糖逗

这道题结合https://fishc.com.cn/thread-168613-1-1.html 再看一下

糖逗

永恒的蓝色梦想 发表于 2020-5-13 14:08
一直搞不懂二叉树……

可能多做几道二叉树的问题会好一些