首页 > 编程语言 >19天【代码随想录算法训练营34期】第六章 二叉树 part06(● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树 )

19天【代码随想录算法训练营34期】第六章 二叉树 part06(● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树 )

时间:2024-04-08 16:12:22浏览次数:26  
标签:None right val self 二叉 搜索 二叉树 root left

654.最大二叉树

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

        max_num = max(nums)
        root = TreeNode(max_num)
        max_index = nums.index(max_num)
        left_nums = nums[:max_index]
        right_nums = nums[max_index+1:]
        root.left = self.constructMaximumBinaryTree(left_nums)
        root.right = self.constructMaximumBinaryTree(right_nums)

        return root

617.合并二叉树

# 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 root1 is None:
            return root2
        if root2 is None:
            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.二叉搜索树中的搜索

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

98.验证二叉搜索树

# 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 __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
        else:
            self.pre = root

        right = self.isValidBST(root.right)

        return left and right

标签:None,right,val,self,二叉,搜索,二叉树,root,left
From: https://www.cnblogs.com/miramira/p/18121509

相关文章

  • 广度优先搜索 Breadth-First Search(BFS)
    问题引入​对于每一个问题,都会有相应的解,在之前的学习中求解的过程,都是以一条条线的形式产生可能解进行筛选验证是否正确。本章节我们来考虑另外一种思路,类似于洪水爆发,从一个源头开始逐渐蔓延开来,直到所有可达的区域都被洪水淹没,所以我们也把这种算法称之为洪泛法。洪泛法会......
  • SHOPEE虾皮API接口:高效获取搜索栏生成的商品结果列表
    一、什么是SHOPEE虾皮API接口?通过SHOPEE虾皮API接口,开发者能够与SHOPEE虾皮平台实现数据交互,获取商品信息、订单数据等,为电商卖家、数据分析师等提供强大的数据支持。二、SHOPEE虾皮API接口核心功能——获取搜索栏生成的商品结果列表我们的SHOPEE虾皮API接口的核心功能是获......
  • 二叉排序树(BST)
    定义二叉排序树是一种特殊的二叉树,其中左子树中的所有节点都小于根节点,右子树中的所有节点都大于根节点(如下图所示)。因此构造过程需要确保插入的元素能够按照这个规则被正确地插入到树中性质1、如果初始状态是一个空树,则插入每个元素的时间复杂度是O(logn),其中n是树中节......
  • 二叉树的非递归遍历
    感谢b站up主优雅的代码:https://space.bilibili.com/95715842二叉树的非递归遍历非递归的先序遍历思想:利用栈先进后出的性质。将根节点入栈,(根节点出栈的同时先拉右子树入栈,之后拉左子树入栈;左子树出栈的同时先拉其右子树入栈);依次继续。voidpreOrder(TreeNode*root){......
  • 数据结构之二叉树 - 超详细的教程,手把手教你认识并运用二叉树
    目录1.树形结构(了解)1.1树形结构的概念(重要)1.2 树的表示形式(了解)1.3 树的应用2.二叉树(重点)2.1概念2.2两种特殊的二叉树2.3二叉树的性质2.4二叉树的存储2.5二叉树的基本操作2.5.1二叉树的遍历1.前序遍历2.中序遍历3.后序遍历4.层序遍历2.5.2......
  • SQL Server在所有表中查找(在整个库搜索内容)
     SQLServer在所有表中查找(在整个库搜索内容)declare@Strnvarchar(max),@tableNamevarchar(50),@colNamevarchar(50),@rowCountintselecta.nametableName,b.nameColname,0asIsFoundinto#t1fromsysobjectsajoinsyscolumnsbona.id=b.idjoinsystypes......
  • 从数组创建二叉树-Leetcode测试用
    Leetcode里和二叉树相关的题目,都是用一个数组表示二叉树的,而这个数组是按照层次优先顺序给出的,连其中的空结点也表示了出来,刚好就是2^N-1个结点,N表示层数。但数组毕竟无法和二叉树一样具有链式结构,无法进行算法测试,因此尝试直接通过这样的数组构建二叉树。通过数组创建这样的二......
  • 全量知识系统 程序详细设计 “三次演算” 再探(Q&A)之2 (百度搜索)
    说明:以下关于全知系统中程序详细设计的沟通是基于今天正在完成中的全量知识系统程序详细设计之“命名法”“正文”的"前言"之1“前提”篇中提出的所有程序要求的基础上的。(这些相同问题的同时沟通 )Q1.这些规则在程序被设计为λ表达式的三个转换规则,分别适用于三条线......
  • 二叉搜索树学习笔记
    二叉搜索树学习笔记\(\frac{11}{20}\),看来是很难完成了。这篇笔记大概是为了Splay准备的。二叉搜索树只需要了解他的思想,结合图片看就很一目了然。一种比较唐的数据结构,他可以维护以下东西:插入/删除一个数。查询某个数是否出现。查询全局某个数的前驱/后继。先考虑每个......
  • 二叉树-统一迭代法
    迭代法实现的前中后序遍历,除了前序和后序相互关联,中序则是另一种风格。我们需要针对三种遍历方式实现统一风格的代码。如何统一风格:解决访问节点(遍历节点)和处理节点(将元素放进结果集)不一致的情况。将访问的节点放入栈中,把要处理的节点放入栈中但是做标记(紧接着放入一个空指针)......