leetcode -- tree 4

# 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(start: int, end: int) -> List[TreeNode]:
            if start > end:
                return [None, ]
            
            allTrees = []

            for i in range(start, end +1):
                leftTrees = generate(start, i - 1)
                rightTrees = generate(i + 1, end)
            
                for l in leftTrees:
                    for r in rightTrees:
                        curnode = TreeNode(i)
                        curnode.left = l
                        curnode.right = r
                        allTrees.append(curnode)

            return allTrees
        
        return generate(1, n) if n else []

class Solution:
    def numTrees(self, n: int) -> int:
        # G(n) == 上界为 n 时 可以构建的二叉搜索树
        G = [0] * (n + 1)
        G[0], G[1] = 1, 1
        for i in range(2, n + 1):
            for j in range(1, n + 1):
                G[i] += G[j - 1] * G[i - j]

        return G[n] 

# 卡兰塔数
        G = 1
        for i in range(0, n):
            G = 2*(2*i + 1) / (i + 2) * G

        return int(G)

# 递归方法 -- 每次传入下层 需要将上层传下来的upper或lower传下去继续进行比较
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def helper(node: Optional[TreeNode], lower = float('-inf'), upper = float('inf')) -> bool:
            if not node:
                return True
            val = node.val

            if val <= lower or val >= upper:
                return False
            
            if not helper(node.left, lower, val):
                return False
            
            if not helper(node.right, val, upper):
                return False

            return True

        return helper(root)
        
# 迭代写法
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        stack, inorder = [], float('-inf')

        while stack or root:
            while root:
                stack.append(root) 
                root = root.left
            root = stack.pop()

            if inorder >= root.val:
                return False

            inorder = root.val
            root = root.right
        
        return True