LC 0095 [M] Unique Binary Search Trees II - ALawliet/algorithms GitHub Wiki

this is just postorder + double nested for loop template that you need to memorize to generate combinations of BSTs

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(nums):
            if not nums:
                return [None]
            
            ans = []
            
            for i in range(len(nums)):
                leftTrees = dfs(nums[:i]) # prefix
                rightTrees = dfs(nums[i+1:]) # suffix
                
                for l in leftTrees:
                    for r in rightTrees:
                        root = TreeNode(nums[i])
                        root.left = l
                        root.right = r
                        ans.append(root)
            
            return ans
        
        nums = range(1, n + 1)
        return dfs(nums)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        def dfs(start, end):
            if start > end:
                return [None]

            res = []

            for i in range(start, end + 1):
                left_subtrees = dfs(start, i - 1) # (i - 1) - 0 + 1
                right_subtrees = dfs(i + 1, end) # (n) - i + 1

                for left_subtree in left_subtrees:
                    for right_subtree in right_subtrees:
                        root = TreeNode(i)
                        root.left = left_subtree 
                        root.right = right_subtree 
                        res.append(root)

            return res
        
        return dfs(1, n) if n else []