Unique Binary Search Tree

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1

    \       /     /      / \      \

     3     2     1      1   3      2

    /     /       \                 \

   2     1         2                 3

思路：dp。设数组res[i]表示n=i时的二叉搜索树个数。

先考虑最简单的情况，res[0] = 0，res[1] = 1。

当n > 1时，一定会存在这样两类二叉搜索树：root节点为1，以及root节点为n本身的树。当root节点为1时，剩下的(n - 1)个节点值全部大于1，都在右孩子的子树里，因此root节点为1的树的总数由规模为n - 1的右孩子子树决定，即个数等于res[n - 1]。当root节点为n时同理，个数也为res[n - 1]。

现在考虑其余节点为root时的情况，假设i为root节点，则值为1到i - 1的节点都会在左孩子子树中，值为i + 1到n的节点都会在右孩子子树中。

因此可能情况是res[i - 1] * res[n - i]。

综上，我们将所有节点为root时的值累加，即为大小为n的二叉搜索树的个数。

 class Solution {

 public:

     int numTrees(int n) {

         vector<int> res(n + , );

         res[] = ;

         for (int i = ; i <= n; i++)

         {

             res[i] = res[i - ] * ;

             for (int j = ; j < i; j++)

                 res[i] += res[j - ] * res[i - j];

         }

         return res[n];

     }

 };

巴特西

Unique Binary Search Tree - Leetcode

最新文章

热门文章