D40bc256e6918f56d757ed83336dc62b
(难度Medium)Problem 95. Unique Binary Search Trees II(不同的二叉搜索树)

链接

Unique Binary Search Trees II - LeetCode

难度等级

Medium

题干

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

题意

给定一个整数n,要求用[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

题解

这又是一道典型的题意简单但是做法比较难的题。

我自己看到题的时候也思考了很久,二叉搜索树不难,但是要生成所有的二叉搜索树就不简单了。因为我们甚至不能直接求出二叉搜索树的数量,更不用说生成了。因为二叉搜索树和元素的排列顺序有关,但却不是强相关的。

比如[2, 1, 3] 和 [2, 3, 1]生成的搜索树是相同的。

而且关键问题是,搜索树是指针构建的,我们也很难直接得出两棵搜索树是否相同。

想到这里,我们可以基本上确定,我们需要在生成搜索树的时候就保证它们都是唯一的。

那么怎么生成,又怎么保证呢?

直接思考是很难的,我们不妨换一个角度。很明显,当n=1的时候,答案是显然的,只有一种情况。当n=2时也并不困难,也就两种。

假设我们拥有了n-1个节点下的搜索树,能不能生成出所有n个节点的生成树呢?如果我们保证生成的时候不会造成重复,是不是就满足题意了呢?

假设n-1的的搜索树是A,那么当n出现之后,其实只有两种情况:

n是根,那么A是n的左子树,或者n出现在A的右子树当中。

n是根的时候,很明显只有一种情况。但是当n出现在A的右子树的时候,情况就不止一种了。因为n可以放在右子树的每一层,每多一层,就有一种放法。

为了保证每个生成树之间不会互相影响,所以我们还需要编写一个拷贝树的函数。虽然思路不难,但是实现起来还是挺麻烦的,具体的细节可以查看下面的代码。

代码

```
/**

  • 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:

    // 拷贝树
    TreeNode* copyTree(TreeNode * rt) {
    if (rt == nullptr) return nullptr;
    TreeNode* nd = new TreeNode(rt->val);
    nd->left = copyTree(rt->left);
    nd->right = copyTree(rt->right);
    return nd;
    }

    void dfs(vector& rt, int n) {
    if (n == 1) {
    TreeNode* root = new TreeNode(1);
    rt.push_back(root);
    return ;
    }
    // 构建n-1个节点的树,插入元素n
    dfs(rt, n-1);
    int m = rt.size();

top Created with Sketch.