当前位置: 首页 > news >正文

搜索+哈希/平衡树,LeetCode 987. 二叉树的垂序遍历

目录

一、题目

1、题目描述

2、接口描述

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解


一、题目

1、题目描述

给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言,其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束,按列索引每一列上的所有结点,形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点,则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

2、接口描述

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> verticalTraversal(TreeNode* root) {}
};

3、原题链接

987. 二叉树的垂序遍历


二、解题报告

1、思路分析

我们由父节点的坐标可以推出左右孩子的坐标,那么我们可以从根节点进行广搜或者深搜,推出所有节点的坐标,然后对每一列按照行坐标和节点值进行排序,记录返回值即可

思路很简单,就是一模拟题,代码或许还可以写的更优雅。

2、复杂度

时间复杂度: O(nlogn)空间复杂度:O(n)

3、代码详解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:
#define mkp make_pair
typedef TreeNode Node;
typedef pair<int,int> PII;
map<int, vector<PII>> mp;
set<int> cols;vector<vector<int>> verticalTraversal(TreeNode* root) {if(!root) return {};mp.clear(), cols.clear();function<void(Node*, const PII&)> dfs = [&](Node* x, const PII& p){mp[p.second].emplace_back(mkp(p.first, x->val));cols.insert(p.second);if(x->left) dfs(x->left, mkp(p.first+1, p.second-1));if(x->right) dfs(x->right, mkp(p.first+1, p.second+1));};dfs(root, mkp(0, 0));vector<vector<int>> ret(cols.size());int tot = 0;for(auto x : cols){sort(mp[x].begin(), mp[x].end());for(auto& p : mp[x])ret[tot].emplace_back(p.second);tot++;}return ret;}
};

相关文章:

搜索+哈希/平衡树,LeetCode 987. 二叉树的垂序遍历

目录 一、题目 1、题目描述 2、接口描述 3、原题链接 二、解题报告 1、思路分析 2、复杂度 3、代码详解 一、题目 1、题目描述 给你二叉树的根结点 root &#xff0c;请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言&#xff0c;其左右子结…...

蓝桥杯每日一题之内存问题

蓝桥杯真题---内存问题 题目描述&#xff1a; 小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。 为了简化问题&#xff0c;变量的类型只有以下三种&#xff1a; int&#xff1a;整型变量&#xff0c;一个 int 型变量占用 4 Byte 的内存空间。 long&#xff…...

Django前后端分离之后端实践2

小实践&#xff1a;实现用户登录、注销及ORM管理功能、事务开启小实践 models.py class Books(models.Model):id models.CharField(primary_keyTrue,max_length20,verbose_name"图书ID")name models.CharField(max_length20,verbose_name图书名称)status models…...

windowsserver 2016 PostgreSQL9.6.3-2升级解决其安全漏洞问题

PostgreSQL 身份验证绕过漏洞(CVE-2017-7546) PostgreSQL 输入验证错误漏洞(CVE-2019-10211) PostgreSQL adminpack扩展安全漏洞(CVE-2018-1115) PostgreSQL 输入验证错误漏洞(CVE-2021-32027) PostgreSQL SQL注入漏洞(CVE-2019-10208) PostgreSQL 安全漏洞(CVE-2018-1058) …...

Java实现免税店商城管理系统 JAVA+Vue+SpringBoot+MySQL

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、系统设计2.1 功能模块设计2.2 研究方法 三、系统展示四、核心代码4.1 查询免税种类4.2 查询物品档案4.3 新增顾客4.4 新增消费记录4.5 审核免税 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的免税店商城管理系…...

【Linux】信号

祝大家新年快乐啦&#xff01;&#xff01;&#xff01;新的一年&#xff0c;第一篇文章我们来谈谈Linux中的信号 目录 一、引入 二、系统内置的信号 三、前台进程和后台进程 四、signal函数 五、信号的产生 5.1 通过终端按键产生信号 5.2 调用系统函数向进程发信号 5…...

[NISACTF 2022]easyssrf

它提示我们输入 那我们输入file:///flag file:// 访问本地文件系统 它提醒我们输file:///fl4g 它提醒我们输ha1x1ux1u.php 看到代码stristr($file, “file”)当我们输入file它会提示我们输了 啥意思可以前面加个/ 也可以通过read读取 思路都是前面加/不等于flag绕过 filephp://…...

在Linux系统中设置全局HTTP代理的步骤与技巧

在Linux系统中&#xff0c;设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问&#xff0c;还可以在某些情况下绕过网络限制或实现匿名上网。下面&#xff0c;我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一&#xf…...

即席查询框架怎么选?

怎么理解即席查询 即席查询&#xff08;Ad Hoc&#xff09;是用户根据自己的需求&#xff0c;灵活的选择查询条件&#xff0c;系统能够根据用户的选择生成相应的统计报表。即席查询与普通应用查询最大的不同是普通的应用查询是定制开发的&#xff0c;而即席查询是由用户自定义查…...

【C语言】实现双向链表

目录 &#xff08;一&#xff09;头文件 &#xff08;二&#xff09; 功能实现 &#xff08;1&#xff09;初始化 &#xff08;2&#xff09;打印链表 &#xff08;3&#xff09; 头插与头删 &#xff08;4&#xff09;尾插与尾删 &#xff08;5&#xff09;指定位置之后…...

Python操作MySQL基础

除了使用图形化工具以外&#xff0c;我们也可以使用编程语言来执行SQL从而操作数据库。在Python中&#xff0c;使用第三方库: pymysql来完成对MySQL数据库的操作。 安装第三方库pymysql 使用命令行,进入cmd&#xff0c;输入命令pip install pymysql. 创建到MySQL的数据库连接…...

【数学建模】【2024年】【第40届】【MCM/ICM】【E题 财产保险的可持续性】【解题思路】

一、题目 &#xff08;一&#xff09; 赛题原文 2024 ICM Problem E: Sustainability of Property Insurance Extreme-weather events are becoming a crisis for property owners and insurers. The world has endured “more than $1 trillion in damages from more than …...

SpringCloud--Eureka注册中心服务搭建注册以及服务发现

注意springboot以及springcloud版本&#xff0c;可能有莫名其妙的错误&#xff0c;这里使用的是springboot-2.6.13&#xff0c;springcloud-2021.0.5 一&#xff0c;Eureka-Server搭建&#xff1a; 1.创建项目&#xff1a;引入依赖 <dependency><groupId>org.sp…...

ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别

这里写目录标题 说明shell模块用法shell 模块和 command 模块的区别 说明 shell模块可以在远程主机上调用shell解释器运行命令&#xff0c;支持shell的各种功能&#xff0c;例如管道等 shell模块用法 ansible slave -m shell -a cat /etc/passwd | grep root # 可以使用管道…...

qss的使用

参考&#xff1a;qss样式表笔记大全(二)&#xff1a;可设置样式的窗口部件列表&#xff08;上&#xff09;&#xff08;持续更新示例&#xff09;_51CTO博客_qss样式...

archlinux 使用 electron-ssr 代理 socks5

提前下载好 pacman 包 https://github.com/shadowsocksrr/electron-ssr/releases/download/v0.2.7/electron-ssr-0.2.7.pacman 首先要有 yay 和 aur 源&#xff0c;这个可以参考我之前的博客 虚拟机内使用 archinstall 安装 arch linux 2024.01.01 安装依赖 yay 安装的&#…...

macos安装local模式spark

文章目录 配置说明安装hadoop安装Spark测试安装成功 配置说明 Scala - 3.18 Spark - 3.5.0 Hadoop - 3.3.6 安装hadoop 从这里下载相应版本的hadoop下载后解压&#xff0c;配置系统环境变量 > sudo vim /etc/profile添加以下两行 export HADOOP_HOME/Users/collinsliu/…...

机器学习算法之支持向量机(SVM)

SVM恐怕大家即使不熟悉&#xff0c;也听说过这个大名吧&#xff0c;这一节我们就介绍这相爱相杀一段内容。 前言&#xff1a;在介绍一个新内容之SVM前&#xff0c;我们不觉映入眼帘的问题是为什么要引入SVM&#xff1f;吃的香&#xff0c;睡的着的情况下&#xff0c;肯定不会是…...

线性判别分析(LDA)

一、说明 LDA 是一种监督降维和分类技术。其主要目的是查找最能分隔数据集中两个或多个类的特征的线性组合。LDA 的主要目标是找到一个较低维度的子空间&#xff0c;该子空间可以最大限度地区分不同类别&#xff0c;同时保留与歧视相关的信息。 LDA 是受监督的&#xff0c;这意…...

Vue 前置导航

Vue 前置导航&#xff08;Vue Front Navigation&#xff09;是一种在 Vue.js 框架中实现导航功能的常见方式。它通常用于构建单页应用程序&#xff08;Single Page Application&#xff09;&#xff0c;通过在页面顶部或侧边栏显示导航菜单&#xff0c;使用户能够轻松切换到不同…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...