二叉树654|617|700|98

654最大二叉树

# 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            root = TreeNode(nums[0])
            return root

        max_val = 0
        max_val_index = 0
        for i in range(len(nums)):
            if nums[i] > max_val:
                max_val = nums[i]
                max_val_index = i
        root = TreeNode(max_val)
        if max_val_index > 0:
            left = nums[:max_val_index]
            root.left = self.constructMaximumBinaryTree(left)
        if max_val_index < len(nums) - 1:
            right = nums[max_val_index + 1:]
            root.right = self.constructMaximumBinaryTree(right)
        return root

617合并二叉树

# 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 mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            root1 = root2
            return root1
        if not root2:
            return root1
        
        root1.val += root2.val
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

700二叉搜索树中的搜索

# 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 searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root or root.val == val:
            return root
        result = None
        if val < root.val:
            result = self.searchBST(root.left, val)
        if val >root.val:
            result = self.searchBST(root.right, val)

        return result

98验证二叉搜索树

# 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 __init__(self):
        self.min_val = float('-inf')
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        left = self.isValidBST(root.left)
        if self.min_val < root.val:
            self.min_val = root.val
        else:
            return False
        right = self.isValidBST(root.right)
        return left and right