95. Unique Binary Search Trees II

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

Python

DFS solution with recursion

class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        if n < 1:
            return []

        return self.generate_dfs(1, n)

    def generate_dfs(self, left: int, right: int):
        if left > right:
            return [None]

        result = []
        for i in range(left, right+1):
            left_nodes = self.generate_dfs(left, i-1)
            right_nodes = self.generate_dfs(i+1, right)
            result += self.generate_tree(
                    root_val=i,
                    left_nodes=left_nodes,
                    right_nodes=right_nodes
                )
        return result

    @staticmethod
    def generate_tree(root_val, left_nodes, right_nodes):
        trees = []
        for l_node in left_nodes:
            for r_node in right_nodes:
                root = TreeNode(root_val)
                root.left = l_node
                root.right = r_node
                trees.append(root)
        return trees