LeetCode 95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

解析：给定一个数值n，计算所有二叉搜索树，这个题目是在LeetCode 96. Unique Binary Search Trees上进行的扩展，前一个题目只是计算所有的数量，这个题目是要获取到所有树。

这种建树问题一般来说都是用递归来解，这道题也不例外，划分左右子树，递归构造。这个其实是用到了大名鼎鼎的分治法 Divide and Conquer。用递归来解，划分左右两个子数组，递归构造。刚开始时，将区间 [1, n] 当作一个整体，然后需要将其中的每个数字都当作根结点，其划分开了左右两个子区间，然后分别调用递归函数，会得到两个结点数组，接下来要做的就是从这两个数组中每次各取一个结点，当作当前根结点的左右子结点，然后将根结点加入结果 result 数组中即可。具体代码如下：

/**
 * 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 ==0)
            return {};
        return helper(1, n);
    }
    vector<TreeNode*> helper(int start, int end)
    {
        vector<TreeNode*> result;
        if(start > end)
            return{nullptr};
        for(int i=start; i <= end; i++)
        {
            auto left = helper(start, i-1);
            auto right = helper(i+1, end);
            for(auto a : left)
            {
                for(auto b : right)
                {
                    TreeNode *node = new TreeNode(i);
                    node->left = a;
                    node->right = b;
                    result.push_back(node);
                }
            }
        }
        return result;
    }
};

参考：

https://www.cnblogs.com/grandyang/p/4301096.html