代码随想录训练营第二十天打卡（Python）｜ 654.最大二叉树 、617.合并二叉树 、700.二叉搜索树中的搜索 、98.验证二叉搜索树

654.最大二叉树
1、使用切片

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 0:
            return None
        max_val = max(nums)
        max_index = nums.index(max_val)
        node = TreeNode(max_val)
        node.left = self.constructMaximumBinaryTree(nums[:max_index])
        node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
        return node

2、基础版

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if len(nums) == 1:
            return TreeNode(nums[0])
        max_val = 0
        max_index = 0
        for i in range(len(nums)):
            if nums[i] > max_val:
                max_val = nums[i]
                max_index = i

        node = TreeNode(max_val)
        if max_index > 0:
            node.left = self.constructMaximumBinaryTree(nums[:max_index])
        if max_index < len(nums) - 1:
            node.right = self.constructMaximumBinaryTree(nums[max_index+1:])
        return node

3、下标法

class Solution:
    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        return self.buildTree(nums, 0, len(nums))

    def buildTree(self, nums, left, right):
        if left >= right:
            return None
        max_val = nums[left]
        max_index = left
        for i in range(left+1, right):
            if nums[i] > max_val:
                max_val = nums[i]
                max_index = i
        node = TreeNode(max_val)
        node.left = self.buildTree(nums, left, max_index)
        node.right = self.buildTree(nums, max_index+1, right)
        return node

617.合并二叉树
1、前序遍历

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1:
            return root2
        if not root2:
            return root1
        node = TreeNode(root1.val+root2.val)
        node.left = self.mergeTrees(root1.left, root2.left)
        node.right = self.mergeTrees(root1.right, root2.right)
        return node

2、迭代法

from collections import deque
class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root1 and not root2:
            return None
        if not root1:
            return root2
        if not root2:
            return root1

        queue = deque()
        queue.append(root1)
        queue.append(root2)
        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()
            if node1.left and node2.left:
                queue.append(node1.left)
                queue.append(node2.left)
            if node1.right and node2.right:
                queue.append(node1.right)
                queue.append(node2.right)

            node1.val = node1.val + node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right

        return root1

700.二叉搜索树中的搜索

1、递归法

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if root is None:
            return None
        if root.val == val:
            return root
        if root.val > val:
            return self.searchBST(root.left, val)
        else:
            return self.searchBST(root.right, val)

2、迭代法

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root:
            if root.val > val:
                root = root.left
            elif root.val < val:
                root = root.right
            else:
                return root
        return None

98.验证二叉搜索树
思路: 二叉搜索树的中序遍历是递增的
1、设定最大的极小值递归法

class Solution:
    def __init__(self):
        self.max_val = float('-inf')

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        left = self.isValidBST(root.left)
        if self.max_val < root.val:
            self.max_val = root.val
        else:
            return False
        right = self.isValidBST(root.right)
        return left and right

2、记录前一个节点的递归法

class Solution:
    def __init__(self):
        self.pre = None # 记录前一个节点

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        left = self.isValidBST(root.left)
        if self.pre and self.pre.val >= root.val:
            return False
        self.pre = root
        right = self.isValidBST(root.right)
        return left and right

3、迭代法

class Solution:

    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True
        stack = []
        res = []
        cur, pre = root, None # cur指向跟节点，pre 记录前一个节点
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                if pre and pre.val >= cur.val:
                    return False
                pre = cur
                cur = cur.right
        return True