代码随想录27期|Python|Day20|654.最大二叉树|617.合并二叉树|700.二叉搜索树中的搜索|98.验证二叉搜索树

2023-12-21 17:59:35

654.?最大二叉树

本题需要注意的是切片操作,可以跟构造二叉树的切片操作对比。

需要注意:

1、构造二叉树只能使用前序遍历的方式;

2、被取出的数组元素(根节点)需要在切片操作的时候被排除

3、循环不变量都是左闭右开区间。

# 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 not nums:
            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

617.?合并二叉树

1、在遍历一个单独的树的时候,终止return None,但是对于两个合并的情况,需要在一棵遍历结束之后转到另外一棵。?相当于“嫁接”

2、返回值选择一棵主要遍历的树。

# 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
        """
        # 终止条件:在一棵遍历到末端的时候转到另外一棵
        if not root1:
            return root2
        if not root2:
            return root1
        # 中间更新:节点值相加
        root1.val += root2.val
        # 递归调用:以root1作为输出的结果
        root1.left = self.mergeTrees(root1.left, root2.left)
        root1.right = self.mergeTrees(root1.right, root2.right)
        return root1

700.?二叉搜索树中的搜索

本题给出两种(递归、迭代)?方法。

1、递归需要新建一个节点result来接收每次递归的返回值

2、搜索二叉树BST满足左侧小,右侧大的条件,所以搜索顺序已经被固定,不需要考虑采用何种搜索顺序;

3、推荐使用迭代。

# 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
        """
        # 迭代
        while root:
            if root.val == val:
                break
            elif root.val > val:
                root = root.left
            else:
                root = root.right
        return root
        
        # 递归
        result = TreeNode(None)  # 新建一个用来储存每次递归返回值的节点
        # 种植条件:空节点or找到该值的节点
        if not root or root.val == val:
            return root
        # 中间更新:小于节点值到右侧找,大于节点值到左侧找
        if root.val > val:
            result = self.searchBST(root.left, val)
        if root.val < val:
            result = self.searchBST(root.right, val)
        # 返回值:找到的节点
        return result

98.?验证二叉搜索树

数组+递归

将二叉树按照中序遍历(左-中-右)保存到一个数组,按照BST的定义现在数组是按照严格单调递增的顺序保存的(等于也是不满足的)。只需要在数组里for循环比较后者是不是大于前者即可。

# 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):
    # 数组保存BST + 递归
    def __init__(self):
        self.vec = []
    
    def traversal(self, node):
        if not node:
            return
        self.traversal(node.left)
        self.vec.append(node.val)  # 先找到最左端,每次依次先保存左子树的值,然后是右子树
        self.traversal(node.right)
    
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.vec = []  # 清空数组
        self.traversal(root)
        for i in range(1, len(self.vec)):  # 需要从1开始
            if self.vec[i - 1] >= self.vec[I]:  # 注意:等于也是不满足
                return False
        return True 

设定+更新最小值

设置全局的最小值(注意!题干给出最小值的下界是int的最小值,所以需要使用float的最小值来初始化)。

和上面方法一样,在遍历的过程中,不断更新max的值,使其始终保持是最大值。

返回结果是中间节点左右的交集,那么只要有一个是false则递归返回到root节点就是fasle。

    def __init__(self):
        self.max_value = float('-inf')  # 因为题干最小值可能是int的最小值

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 递归(设定最小值)
        if not root:
            return True  # 空树也是BST
        left = self.isValidBST(root.left)  # 向左遍历,返回值是bool
        # 更新max值:
        if root.val > self.max_value:  # 如果当前节点的值比max大,那么赋值给max,保持max是现在最大的值
            self.max_value = root.val
        else:  # 不满足直接返回false
            return False
        right = self.isValidBST(root.right)  # 向右遍历,返回值是bool,逻辑和上面的一样

        return left and right  # root节点返回值是left和right的交集

双指针思路

一个全局的指针pre指向上一个root节点,一个指针在递归函数里指向当前的root节点,保持root的值始终大于pre。

和保存到数组后用for处理比较像,但是可以直接在BST中处理,不需要单独开内存。

    def __init__(self):
        self.vec = []
        self.max_value = float('-inf')  # 因为题干最小值可能是int的最小值
        self.pre = None

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        # 记录比较前一个节点
        if not root:
            return True
        left = self.isValidBST(root.left)
        # 双指针思路,一个指向当前的root,一个保存的是上一个遍历的root的pre,保持root的值始终大于pre的值
        if self.pre is not None and self.pre.val >= root.val:  # not None是因为初始化pre为None需要在赋值之后才可以比较val
            return False
        self.pre = root
        right = self.isValidBST(root.right)

第19天完结🎉

文章来源:https://blog.csdn.net/m0_57527624/article/details/135123531
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。