95.不同的二叉搜索树

一、问题描述

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

示例:

输入: 3
输出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

二、问题解析

二叉查找树

  (Binary Search Tree，又名：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树：

  1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3.它的左、右子树也分别为二叉排序树。

分治法

  基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同的或相似的子问题，知道最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

 1、分解：按数字范围逐个按参照数进行分解为左右两部分，分别求解

 2、解决：实现递归函数，将分解后的数字范围作为参数，返回结果

 3、合并：将返回的结果进行合并，以参照数作为根节点，左范围作为左子树，右范围作为右子树

三、代码示例

 /*
 @start 整数起点
 @end    整数终点
 Description:采用分治法处理该问题，以每个整数作为根节点，
 比该整数小的作为左子树，比该整数打的右子树。
 */
vector<TreeNode*> generateSubTrees(int start, int end) {
    vector<TreeNode*> sub = {};
    //起点大于终点 无法生成搜索树
    if (start > end) { 
        sub.push_back(NULL);
        return sub; 
    }
    //start --- end 皆可作为根节点（满足左小右大原则即可）
    for (int i = start; i <= end; i++) {
        //比i小的作为左子树
        vector<TreeNode*>  leftTrees = generateSubTrees(start, i-1);
        //比i大的作为右子树
        vector<TreeNode*>  rightTrees = generateSubTrees(i+1, end);

        //左右子树的所有可能进行笛卡尔积
        for (TreeNode* l : leftTrees) {
            for (TreeNode* r : rightTrees) {
                //i作为根节点
                TreeNode* root = new TreeNode(i);
                root->left = l;
                root->right = r;
                sub.push_back(root);
            }
        }
    }
    return sub;
}

vector<TreeNode*> generateTrees(int n) {
    if (n < 1) {
        vector<TreeNode*> tree = {NULL};
        return tree;
    }
    return generateSubTrees(1, n);
}