代码随想录第十七天刷题

def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            return TreeNode(nums[0])
        node = TreeNode(0)

        maxValue = 0
        maxValueIndex = 0
        for i in range(len(nums)):
            if nums[i] > maxValue:
                maxValue = nums[i]
                maxValueIndex = i
        node.val = maxValue

        if maxValueIndex > 0:
            new_list = nums[:maxValueIndex]
            node.left = self.constructMaximumBinaryTree(new_list)

        if maxValueIndex < len(nums) - 1:
            new_list = nums[maxValueIndex + 1:]
            node.right = self.constructMaximumBinaryTree(new_list)
        return node


# ---------- 返回值类型注解 ----------
# def f() -> TreeNode:
#     表示：这个函数返回 TreeNode 对象
#
# -> 是“返回类型提示”
# 不是语法强制
# 是给人看的提示

# ---------- 递归终止条件 ----------
# 最大二叉树递归终止：
# 1. 数组为空 → 不处理
# 2. 数组长度为 1 → 直接创建叶子节点
#
# 为什么要判断长度 1？
# 因为长度为 1 时，左右子数组都为空
# 直接结束递归

# ---------- 最大二叉树的初始化 ----------
# node = TreeNode(0)  # 根节点占位
# maxValue = 0        # 存最大值（可能有 bug）
# maxValueIndex = 0   # 存下标
#本道题目有说都是正整数
# 正确的初始化：
# maxValue = nums[0] 或 float('-inf')


# ---------- 最大二叉树的核心 ----------
# 1. 遍历数组找最大值
# 2. 记录最大值和下标
# 3. 用最大值作为节点值
#
# 这是“自顶向下”递归的起点

# ---------- 递归合并二叉树 ----------
# root1.left = merge(root1.left, root2.left)
#     含义：合并两棵树的左子树，结果作为 root1 的左孩子
#
# 递归的精髓：
# 大问题 → 小问题
# 合并整棵树 → 合并左右子树

# ---------- BST 搜索 ----------
# if root.val > val:
#     return searchBST(root.left, val)
#
# 含义：
# 1. 在左子树中继续找
# 2. 返回找到的节点
#
# 为什么能返回“子树”？
# 因为 BST 节点天然链接它的孩子
# 返回一个节点 = 返回以它为根的子树