题目描述

给定一个整数 $n$，返回所有结构不同的 BST （二叉搜索树），满足中序遍历是 $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

算法

(DFS) $O(C_{2n}^n/(n+1))$

递归搜索所有方案。

1. 对于每段连续的序列 $l, l + 1, … r$，枚举二叉搜索树根节点的位置；
2. 分别递归求出左右子树的所有方案；
3. 左子树的任意一种方案和右子树的任意一种方案拼在一起，可以得到当前节点的一种方案，所以我们将左右子树的所有方案两两组合，并记录在答案中。

时间复杂度分析：我们来求一下当节点数是 $n$ 时，总共有多少种方案。假设方案数是 $h_n$，则有 $h_n = \sum_{k=0}^{n-1}h_k*h_{n-1-k}$。所以 $h_n$ 是卡特兰数，其通项公式是 $h_n = C_{2n}^n/(n+1)$。所以时间复杂度是 $O(C_{2n}^n/(n+1))$。

C++ 代码

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

    vector<TreeNode*> dfs(int l, int r)
    {
        vector<TreeNode*>res;
        if (l > r)
        {
            res.push_back(NULL);
            return res;
        }
        for (int i = l; i <= r; i ++ )
        {
            vector<TreeNode*>left = dfs(l, i - 1)
                , right = dfs(i + 1, r);
            for (auto &lc : left)
                for (auto &rc : right)
                {
                    TreeNode *root = new TreeNode(i);
                    root->left = lc;
                    root->right = rc;
                    res.push_back(root);
                }
        }
        return res;
    }
};