1
class Solution:
2
    # 使用前序遍历：根 -> 左 -> 右
3
    # 每次找到数组中最大值作为根节点，递归构建左右子树
4
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
5
        return self.build(nums, 0, len(nums) - 1)
6

7
    def build(self, nums, l, r):
8
        if l > r:
9
            return None
10
        index = -1  # 标记最大值索引
11
        max_val = float('-inf')
12
        for i in range(l, r + 1):
13
            if max_val < nums[i]:
14
                index = i
15
                max_val = nums[i]
16
        root = TreeNode(max_val)
17
        root.left = self.build(nums, l, index - 1)
18
        root.right = self.build(nums, index + 1, r)
19
        return root

1
class Solution:
2
    # 若两个节点都存在，则值相加
3
    # 若其中一个不存在，返回另一个
4
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
5
        if not root1:
6
            return root2
7
        if not root2:
8
            return root1
9
        root1.val += root2.val
10
        root1.left = self.mergeTrees(root1.left, root2.left)
11
        root1.right = self.mergeTrees(root1.right, root2.right)
12
        return root1

1
class Solution:
2
    # 利用二叉搜索树特性：
3
    # 左子树 < 根节点 < 右子树
4
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
5
        if not root:
6
            return None
7
        if val > root.val:
8
            return self.searchBST(root.right, val)
9
        if val < root.val:
10
            return self.searchBST(root.left, val)
11
        return root

1
class Solution:
2
    # 每个节点必须满足 min < node.val < max 的条件
3
    # 递归向下更新 min/max 限制区间
4
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
5
        return self.isValid(root, None, None)
6

7
    def isValid(self, root, min_node, max_node):
8
        if not root:
9
            return True
10
        if min_node is not None and root.val <= min_node.val:
11
            return False
12
        if max_node is not None and root.val >= max_node.val:
13
            return False
14
        return self.isValid(root.left, min_node, root) and self.isValid(root.right, root, max_node)