95. Unique Binary Search Trees II

Problem Statement

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

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example:

Input: n = 3 Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Input: n = 1 Output: [[1]]

Solution Approach

The solution employs recursion and backtracking to generate all possible combinations of BSTs for a given number of nodes.

Algorithm

1. The gen function recursively calculates possible BST combinations for a given range of values.
2. For each value i in the range, it treats i as a root and recursively generates left and right subtrees using values before and after i, respectively.
3. For every combination of left and right subtrees, a new BST is formed with i as root and added to the list of BSTs for the current range.

Implement

    class Solution:
      def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
      def gen(l, r):
          tmp = []
          if l > r:
              return [None]
          for i in range(l, r + 1):
              left = gen(l, i - 1)
              right = gen(i + 1, r)
              
              for lN in left:
                  for rN in right:
                      node = TreeNode(i)
                      node.left = lN
                      node.right = rN
                      tmp.append(node)
          return tmp

      return gen(1, n)
 

    
    

Twitter  facebook  Email