代码随想录算法训练营第13天|二叉树基础知识、递归遍历、迭代遍历、层序遍历、116. 填充每个节点的下一个右侧节点指针

目录

  • 二叉树基础
    • 深度和高度
    • 满二叉树和完全二叉树
    • 二叉搜索树和平衡二叉搜索树
    • 二叉树节点定义
    • 前中后序遍历
  • 递归遍历
    • 前序递归遍历—144. 二叉树的前序遍历
  • 迭代遍历
  • 层序遍历
  • 116. 填充每个节点的下一个右侧节点指针
    • 1、题目描述
    • 2、思路
    • 3、code

二叉树基础

深度和高度

在这里插入图片描述

满二叉树和完全二叉树

满二叉树:除了根节点,每个节点都有两个孩子
完全二叉树:除了最底下的右侧节点可能没填满外,其余每层节点数都达到最大值。

二叉搜索树和平衡二叉搜索树

二叉搜索树:左节点小于根节点,有节点大于根节点
平衡二叉搜索树:在二叉搜索树的基础上,左右两个子树的高度差的不超过1

二叉树节点定义

class TreeNode:def __init__(self, val, left = None, right = None):self.left = leftself.right = rightself.val = val

前中后序遍历

  • 前序遍历:中左右
  • 中序遍历:左中右
  • 后序遍历:左右中
    在这里插入图片描述

递归遍历

前序递归遍历—144. 二叉树的前序遍历

题目链接:添加链接描述
在这里插入图片描述

class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(node,res):if node == None:return # 前序:中左右res.append(node.val)dfs(node.left,res)dfs(node.right,res)return resres = dfs(root,[])return res

迭代遍历

前序遍历是中左右,每次先处理的是中间节点,再处理左节点,最后右节点

设计一个栈:先将根节点放入栈中,然后将右孩子加入栈,再加入左孩子

Q:为什么要先加入 右孩子,再加入左孩子呢?

A:因为这样出栈的时候才是中左右的顺序

thon
class Solution:def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:# 前序遍历:中左右# 迭代法:使用栈if not root:return []stack = []vec = []# 先把根节点压入栈中stack.append(root)while len(stack) != 0:# 先弹出栈首node = stack.pop()# 把栈首弹出节点的val记录到vec中vec.append(node.val)# 然后压入此时栈首的左右孩子# 要先压入右孩子,才能先弹出左孩子if node.right:stack.append(node.right)if node.left:stack.append(node.left)return vec

层序遍历

在这里插入图片描述
在这里插入图片描述

116. 填充每个节点的下一个右侧节点指针

题目链接:

1、题目描述

在这里插入图片描述输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,‘#’ 标志着每一层的结束。

2、思路

层序遍历

3、code

"""
# Definition for a Node.
class Node:def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):self.val = valself.left = leftself.right = rightself.next = next
"""
from collections import deque
class Solution:def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':queue = deque()if root != None:queue.append(root)else:return rootwhile len(queue)!=0:size = len(queue)while size != 0:node = queue.popleft()if size == 1:node.next = Noneelse:node_next = queue[0] # 查看队列出队元素node.next = node_nextif node.left is not None:queue.append(node.left)if node.right is not None:queue.append(node.right)size -= 1return root               

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/423309.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

XSS跨站脚本攻击及防护

什么是XSS攻击? XSS(Cross-Site Scripting,跨站脚本攻击)是一种代码注入攻击。攻击者在目标网站上注入恶意代码,当用户(被攻击者)登录网站时就会执行这些恶意代码,通过这些脚本可以读取cookie,session tokens,或者网站其他敏感的网…

Ubuntu WSL使用技巧

0 Preface/Foreword 1 默认为root用户 当下载完成Ubuntu之后,首次登录,当完成初始化后,提示输入新的用户名时候,直接点击右上角的X按钮,再重新登陆,系统会默认使用root权限登录。 2 root用户和普通用户切换…

阿里云社区领积分自动打卡Selenium IDE脚本

脚本 感觉打卡比较麻烦,要点开点按钮这种机械化的操作。 所以就自己整了个脚本: { “id”: “f9999777-9ad6-40e0-9435-4f105919c982”, “version”: “2.0”, “name”: “aliyun”, “url”: “https://developer.aliyun.com”, “tests”: [{ “id”…

ubuntu22安装docker

1、查看服务器系统信息 uname -a:显示内核名称、主机名、内核版本、处理器类型等信息。 lsb_release -a:显示有关 Ubuntu 发行版的详细信息,包括版本号、代号等。 free -h:查看系统内存使用情况。 df -h:查看磁盘空间使…

Vue2时间轴组件(TimeLine/分页、自动顺序播放、暂停、换肤功能、时间选择,鼠标快速滑动)

目录 1介绍背景 2实现原理 3组件介绍 4代码 5其他说明 1介绍背景 项目背景是 一天的时间轴 10分钟为一间隔 一天被划分成144个节点 一页面12个节点 代码介绍的很详细 可参考或者借鉴 2实现原理 对Element-plus滑块组件的二次封装 基于Vue2(2.6.14&#x…

Vue3 : ref 与 reactive

目录 一.ref 二.reactive 三.ref与reactive的区别 四.总结 一.ref 在 Vue 3 中,ref 是一个用于创建可读写且支持数据跟踪的响应式引用对象。它主要用于在组件内部创建响应式数据,这些数据可以是基本类型(如 number、string、boolean&…

深入理解全连接层:从线性代数到 PyTorch 中的 nn.Linear 和 nn.Parameter

文章目录 数学概念(全连接层,线性层)nn.Linear()nn.Parameter()Q1. 为什么 self.weight 的权重矩阵 shape 使用 ( out_features , in_features ) (\text{out\_features}, \text{in\_features}) (out_features,in_features)而不是 ( in_featur…

Vue的缓存组件 | 详解KeepAlive

引言 在Vue开发中,我们经常需要处理大量的组件渲染和销毁操作,这可能会影响应用的性能和用户体验。而Vue的KeepAlive组件提供了一种简便的方式来优化组件的渲染和销毁流程,通过缓存已经渲染的组件来提升应用的性能。 本文将详细介绍Vue的Ke…

即插即用篇 | YOLOv10 引入矩形自校准模块RCM | ECCV 2024

本改进已同步到YOLO-Magic框架! 语义分割是许多应用的重要任务,但要在有限的计算成本下实现先进性能仍然非常具有挑战性。在本文中,我们提出了CGRSeg,一个基于上下文引导的空间特征重建的高效且具有竞争力的分割框架。我们精心设计了一个矩形自校准模块,用于空间特征重建和…

经典RNA-seq分析流程1

RNA-seq分析有很多流程, 一般都是上游linux工具获取表达矩阵数据,然后就可以使用下游R包进行处理了,要么是差异DEG表达gene等分析; 因为下游分析其实R包是明确的,毕竟有很多生信分析教程,但是上游的linux…

无人机之处理器篇

无人机的处理器是无人机系统的核心部件之一,它负责控制无人机的飞行、数据处理、任务执行等多个关键功能。以下是对无人机处理器的详细解析: 一、处理器类型 无人机中使用的处理器主要包括以下几种类型: CPU处理器:CPU是无人机的…

神经网络多层感知器异或问题求解-学习篇

多层感知器可以解决单层感知器无法解决的异或问题 首先给了四个输入样本,输入样本和位置信息如下所示,现在要学习一个模型,在二维空间中把两个样本分开,输入数据是个矩阵,矩阵中有四个样本,样本的维度是三维…

Unity全面取消Runtime费用 安装游戏不再收版费

Unity宣布他们已经废除了争议性的Runtime费用,该费用于2023年9月引入,定于1月1日开始收取。Runtime费用起初是打算根据使用Unity引擎安装游戏的次数收取版权费。2023年9月晚些时候,该公司部分收回了计划,称Runtime费用只适用于订阅…

[数据集][目标检测]车窗状态检测车窗开关检测数据集VOC+YOLO格式299张3类别

数据集格式:Pascal VOC格式YOLO格式(不包含分割路径的txt文件,仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数):299 标注数量(xml文件个数):299 标注数量(txt文件个数):299 标注类别…

应用程序已被 Java 安全阻止:Java 安全中的添加的例外站点如何对所有用户生效

如题:应用程序已被 Java 安全阻止,如下图所示: 在寻找全局配置的时候花了一个上午的时间,到处搜解决方法,都不可行。最后还是参考官方的文档配置好了。如果你碰到了同样的问题,这篇文章一定可以帮到你。 环…

论文阅读:AutoDIR Automatic All-in-One Image Restoration with Latent Diffusion

论文阅读:AutoDIR: Automatic All-in-One Image Restoration with Latent Diffusion 这是 ECCV 2024 的一篇文章,利用扩散模型实现图像恢复的任务。 Abstract 这篇文章提出了一个创新的 all-in-one 的图像恢复框架,融合了隐扩散技术&#x…

【重学 MySQL】二十八、SQL99语法新特性之自然连接和 using 连接

【重学 MySQL】二十八、SQL99语法新特性之自然连接和 using 连接 自然连接(NATURAL JOIN)USING连接总结 SQL99语法在SQL92的基础上引入了一些新特性,其中自然连接(NATURAL JOIN)和USING连接是较为显著的两个特性。 自…

《数字图像处理(面向新工科的电工电子信息基础课程系列教材)》P84

更正卷积与相关微课中互相关运算动画中的索引。 1-D correlation rectwave 禹晶、肖创柏、廖庆敏《数字图像处理(面向新工科的电工电子信息基础课程系列教材)》 禹晶、肖创柏、廖庆敏《数字图像处理》资源二维码

性能测试【Locust】基本使用介绍

一.前言 Locust是一款易于使用的分布式负载测试工具,基于事件驱动,使用轻量级执行单元(如协程)来实现高并发。 二.基本使用 以下是Locust性能测试使用的一个基础Demo示例,该示例有安装Locust、编写测试脚本、启动测…

三方共建 | 网络安全运营中心正式揭牌成立

9月3日,广州迎来了一场网络安全领域的盛事。悦学科技、聚铭网络、微步在线联合打造的7x24小时网络安全运营中心(以下简称“中心”)正式成立,并在现场举行了庄重而热烈的揭牌仪式。众多行业专家、企业代表齐聚一堂,共同…