96. Unique Binary Search Trees

Posted on Edited on In

96. Unique Binary Search Trees

Description

Difficulty: Medium

Related Topics: Math, Dynamic Programming, Tree, Binary Search Tree, Binary Tree

Given an integer n, return the number of structurally unique **BST’**s (binary search trees) which has exactly n nodes of unique values from 1 to n.

Example 1:

1
2
Input: n = 3
Output: 5

Example 2:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 19

Hints/Notes

  • Draw the tree
  • Dynamic programming

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<vector<int>> memo;

    int numTrees(int n) {
        memo = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
        return count(1, n);
    }

    int count(int low, int high) {
        if (low >= high) {
            return 1;
        }

        if (memo[low][high] != 0) {
            return memo[low][high];
        }

        int sum = 0;
        for (int i = low; i <= high; i++) {
            int left = count(low, i - 1);
            int right = count(i + 1, high);
            sum += left * right;
        }
        memo[low][high] = sum;
        return sum;
    }
};