代码随想录算法训练营第十七天| 二叉树5

654. 最大二叉树

又是构造二叉树，昨天大家刚刚做完中序后序确定二叉树，今天做这个应该会容易一些，先看视频，好好体会一下为什么构造二叉树都是前序遍历

题目链接/文章讲解：代码随想录

视频讲解：又是构造二叉树，又有很多坑！| LeetCode：654.最大二叉树_哔哩哔哩_bilibili

nums[:maxValueIndex]是一个切片，创建一个新列表，取的是nums开头到索引为maxValueIndex-1位置

# 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:return TreeNode(nums[0])node=TreeNode(0)maxValue=0maxValueIndex=0for i in range(len(nums)):if nums[i]>maxValue:maxValue=nums[i]maxValueIndex=inode.val=maxValueif maxValueIndex>0:new_list=nums[:maxValueIndex]node.left=self.constructMaximumBinaryTree(new_list)if maxValueIndex<len(nums)- 1:new_list=nums[maxValueIndex+1:]node.right=self.constructMaximumBinaryTree(new_list)return node

617. 合并二叉树

这次是一起操作两个二叉树了，估计大家也没一起操作过两个二叉树，也不知道该如何一起操作，可以看视频先理解一下。优先掌握递归。

题目链接/文章讲解：代码随想录

视频讲解：一起操作两个二叉树？有点懵！| LeetCode：617.合并二叉树_哔哩哔哩_bilibili

不建立新的树，配合递归

# 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:return root2if not root2:return root1root1.val+=root2.valroot1.left=self.mergeTrees(root1.left,root2.left)root1.right=self.mergeTrees(root1.right,root2.right)return root1

700. 二叉搜索树中的搜索

递归和迭代都可以掌握以下，因为本题比较简单，了解一下二叉搜索树的特性

题目链接/文章讲解: 代码随想录

视频讲解：不愧是搜索树，这次搜索有方向了！| LeetCode：700.二叉搜索树中的搜索_哔哩哔哩_bilibili

二叉搜索树（BST） 是一种特殊的二叉树，它满足以下性质：

左子树的所有节点值 小于 根节点值。
右子树的所有节点值 大于 根节点值。
每个子树 也是一棵二叉搜索树（递归定义）。

递归：

# 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 rootif root.val<val:return self.searchBST(root.right,val)if root.val>val:return self.searchBST(root.left,val)

迭代：

# 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]:while root:if root.val>val:root=root.leftelif root.val<val:root=root.rightelse:return rootreturn root

98. 验证二叉搜索树

遇到搜索树，一定想着中序遍历，这样才能利用上特性。

但本题是有陷阱的，可以自己先做一做，然后在看题解，看看自己是不是掉陷阱里了。这样理解的更深刻。

题目链接/文章讲解：代码随想录

视频讲解：你对二叉搜索树了解的还不够！ | LeetCode：98.验证二叉搜索树_哔哩哔哩_bilibili

递归，注意不是仅判断相邻节点，需判断每个节点和根节点比较

# 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 isValidBST(self, root: Optional[TreeNode]) -> bool:def validate(node,min_val,max_val):if not node:return Trueif not (min_val<node.val<max_val):return Falsereturn validate(node.left,min_val,node.val) and validate(node.right,node.val,max_val)return validate(root,float('-inf'),float('inf'))