95. Unique Binary Search Trees II - Explanation

# 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 generate(left, right):
            if left > right:
                return [None]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)
            return res

        return generate(1, n)

# 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]]:
        dp = {}

        def generate(left, right):
            if left > right:
                return [None]
            if (left, right) in dp:
                return dp[(left, right)]

            res = []
            for val in range(left, right + 1):
                for leftTree in generate(left, val - 1):
                    for rightTree in generate(val + 1, right):
                        root = TreeNode(val, leftTree, rightTree)
                        res.append(root)

            dp[(left, right)] = res
            return res

        return generate(1, n)

# 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]]:
        dp = [[[] for _ in range(n + 2)] for _ in range(n + 2)]
        for i in range(1, n + 2):
            dp[i][i - 1] = [None]

        for length in range(1, n + 1):
            for left in range(1, n - length + 2):
                right = left + length - 1
                dp[left][right] = []
                for val in range(left, right + 1):
                    for leftTree in dp[left][val - 1]:
                        for rightTree in dp[val + 1][right]:
                            root = TreeNode(val, leftTree, rightTree)
                            dp[left][right].append(root)

        return dp[1][n]

# 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]]:
        dp = [[] for _ in range(n + 1)]
        dp[0] = [None]

        for length in range(1, n + 1):
            dp[length] = []
            for val in range(1, length + 1):
                for leftTree in dp[val - 1]:
                    for rightTree in dp[length - val]:
                        root = TreeNode(val)
                        root.left = leftTree
                        root.right = self.shift(rightTree, val)
                        dp[length].append(root)

        return dp[n]

    def shift(self, node: Optional[TreeNode], offset: int) -> Optional[TreeNode]:
        if not node:
            return None
        root = TreeNode(node.val + offset)
        root.left = self.shift(node.left, offset)
        root.right = self.shift(node.right, offset)
        return root