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

654.最大二叉树

和构造二叉树差不多，本题使用索引的方式

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:return self.traversal(nums, 0, len(nums)-1)def traversal(self, nums, left, right):if left > right:returnmax_value_index = leftfor index in range(left+1, right+1):if nums[index] > nums[max_value_index]:max_value_index = indexroot = TreeNode(nums[max_value_index])root.left = self.traversal(nums, left, max_value_index-1)root.right = self.traversal(nums, max_value_index+1, right)return root      

617.合并二叉树

最后合成的树放在root1上

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

700.二叉搜索树中的搜索

搜索二叉树左子树的值都比根节点小，右子树的值都是根节点大，利用这个特性将大大提高搜索效率

递归法

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:returnif root.val == val:return rootif root.val > val:return self.searchBST(root.left, val)if root.val < val:return self.searchBST(root.right, val)

迭代法

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:while root:if root.val == val:return rootelif root.val > val:root = root.leftelse:root = root.rightreturn

98.验证二叉搜索树

此题不能单纯比较根节点大于左节点小于右节点，因为二叉搜索树需要左子树所有的节点都小于根节点，右子树所有的节点都大于根节点

本题使用中序遍历，如果是二叉搜索树的话，可以得到递增序列。因此在中序遍历中比较当前值是否大于前一个值，如果不满足，则返回False

class Solution:def __init__(self):self.pre = Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:if not root:return Trueleft = self.isValidBST(root.left)if self.pre is not None and root.val <= self.pre:return Falseself.pre = root.valright = self.isValidBST(root.right)return left and right

注意：本题中if self.pre is not None 不能替换为if self.pre，因为pre为0的时候，if self.pre 是False