代码随想录算法训练营第十七天| 二叉树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=0
        maxValueIndex=0
        for i in range(len(nums)):
            if nums[i]>maxValue:
                maxValue=nums[i]
                maxValueIndex=i
        node.val=maxValue
        if 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 root2
        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. 二叉搜索树中的搜索

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

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

视频讲解：不愧是搜索树，这次搜索有方向了！| 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 root
        if 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.left
            elif root.val<val:
                root=root.right
            else:
                return root
        return 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 True
            if not (min_val<node.val<max_val):
                return False
            return validate(node.left,min_val,node.val) and validate(node.right,node.val,max_val)
        return validate(root,float('-inf'),float('inf'))