代码随想录算法训练营day17| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜索 98.验证二叉搜索树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        if len(nums) == 1:
            return TreeNode(nums[0])
        
        # 如果不止一个节点，设置二叉树初始值为0，一般无左右子树
        node = TreeNode(0)

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

        # 构建左子树
        if max_idx > 0: # 排除没有左子树的情况
            left_ls = nums[:max_idx]
            node.left = self.constructMaximumBinaryTree(left_ls)   # 递归
        # 构建右子树
        if max_idx < len(nums)-1:
            right_ls = nums[max_idx+1:]
            node.right = self.constructMaximumBinaryTree(right_ls)
        
        return node
        

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: TreeNode
        :type root2: TreeNode
        :rtype: TreeNode
        """
        # 终止条件：如果root1没有根节点就说明root1对应的二叉树为None，那相加就是root2对应的二叉树咯
        if not root1:
            return root2
        if not root2:
            return root1
        
        # 根：本题选择就在root1基础上进行修改，选择前序：根左右
        root1.val += root2.val

        # 递归法：我认为就是左子节点的处理方式与根节点一样，还是用mergeTrees，对应参数变成了root1.left和root2.left
        root1.left = self.mergeTrees(root1.left, root2.left)
        # 右子树同理
        root1.right = self.mergeTrees(root1.right, root2.right)
        # 返回值：修改后的root1
        return root1
        

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: TreeNode
        :type val: int
        :rtype: TreeNode
        """
        # 如果root不存在或者根节点的值正好为目标值，则都是返回根节点，终止
        if root == None or root.val == val:
            return root
        # 二叉搜索树的特性：左<根<右
        # so, 当目标值小于根，就向左边遍历，这是一定的。
        if val < root.val:
            result = self.searchBST(root.left, val)
        # 右边同理
        if val > root.val:
            result = self.searchBST(root.right, val)
        return result

        

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def __init__(self):
        self.pre = None # 设置最小值初值

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 双指针法，pre-->root这种顺序，每次向后移动，如果一直保持pre.val<root.val则满足二叉搜索树的特性
        # 要用中序遍历来判断二叉搜索树，则示例2中递归的顺序是：1-->5-->3-->4-->5，一看就发现第二个大于第三个，返回False
        if not root:
            return True
        # 递归+中序
        # 左
        left = self.isValidBST(root.left)
        # 根
        if self.pre != None and self.pre.val >= root.val:
            return False
        self.pre = root  # 向后移动指针
        # 右
        right = self.isValidBST(root.right)
        return left and right