• 困难
  • 中等
  • 简单

    题目描述

    给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。

    来源，leetcode 每日一题 95. 不同的二叉搜索树 II

示例：

  1. 输入：3
  2. 输出：
  3. [
  4.   [1,null,3,2],
  5.   [3,2,null,1],
  6.   [3,1,null,null,2],
  7.   [2,1,3],
  8.   [1,null,2,null,3]
  9. ]
  10. 解释：
  11. 以上的输出对应以下 5 种不同结构的二叉搜索树：
  13.    1         3     3      2      1
  14.     \       /     /      / \      \
  15.      3     2     1      1   3      2
  16.     /     /       \                 \
  17.    2     1         2                 3
  19. 来源：力扣（LeetCode）
  20. 链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
  21. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

  1. 递归的想法，二叉树是有序树，对于一棵树而言，当第i个节点为根时，其将[1,i-1]和[i+1, n]分成了两个子树，则此时只需要对两个子树分别构建，然后将他们拼接到i上即可。

  2. 需要学会问题分解！

    代码

    /**
* 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*> genTree(int start, int end) {
     if (start > end) {
         return {nullptr};
     }
     vector<TreeNode*> result;
     for (int i = start; i <= end; i++) {
         vector<TreeNode*> left = genTree(start, i-1);
         vector<TreeNode*> right = genTree(i+1, end);
         for (auto& item_l:left) {
             for (auto& item_r:right) {
                 TreeNode* root = new TreeNode(i);
                 root->left = item_l;
                 root->right = item_r;
                 result.emplace_back(root);
             }
         }
     }

     return result;
 }
 vector<TreeNode*> generateTrees(int n) {
     if (n == 0) {
         return vector<TreeNode*>();
     }
     return genTree(1, n);

 }
};