LeetCode 96. Unique Binary Search Trees

Description

https://leetcode.com/problems/unique-binary-search-trees/

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:

Input: n = 3
Output: 5

Example 2:

Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 19

Explanation

For 0 <= i <= n, all values less than i go to the left tree, all values greater than i go to the right tree. Count how many possible ways to build a left tree and how many possible ways to build a right tree, and multiply the count to get the result.

Python Solution

class Solution:
    def numTrees(self, n: int) -> int:
        
        results = {
            0: 1,
            1: 1,
            2: 2
        }
        
        return self.helper(n, results)
        
        
    def helper(self, n , results):
        if n in results:
            return results[n]
        else:    
            result = 0
            
            for i in range(n):
                result += self.helper(i, results) * self.helper(n - i - 1, results)
            results[n] = result
        
            return result
        
        
  • Time Complexity: O(N^2).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published. Required fields are marked *