搜索+哈希/平衡树,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 ,请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言,其左右子结…...
蓝桥杯每日一题之内存问题
蓝桥杯真题---内存问题 题目描述: 小蓝最近总喜欢计算自己的代码中定义的变量占用了多少内存空间。 为了简化问题,变量的类型只有以下三种: int:整型变量,一个 int 型变量占用 4 Byte 的内存空间。 longÿ…...
Django前后端分离之后端实践2
小实践:实现用户登录、注销及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】信号
祝大家新年快乐啦!!!新的一年,第一篇文章我们来谈谈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系统中,设置全局HTTP代理可以方便我们统一管理和控制网络请求。这不仅可以帮助我们加速网络访问,还可以在某些情况下绕过网络限制或实现匿名上网。下面,我将为你详细介绍在Linux系统中设置全局HTTP代理的步骤与技巧。 步骤一…...
即席查询框架怎么选?
怎么理解即席查询 即席查询(Ad Hoc)是用户根据自己的需求,灵活的选择查询条件,系统能够根据用户的选择生成相应的统计报表。即席查询与普通应用查询最大的不同是普通的应用查询是定制开发的,而即席查询是由用户自定义查…...
【C语言】实现双向链表
目录 (一)头文件 (二) 功能实现 (1)初始化 (2)打印链表 (3) 头插与头删 (4)尾插与尾删 (5)指定位置之后…...
Python操作MySQL基础
除了使用图形化工具以外,我们也可以使用编程语言来执行SQL从而操作数据库。在Python中,使用第三方库: pymysql来完成对MySQL数据库的操作。 安装第三方库pymysql 使用命令行,进入cmd,输入命令pip install pymysql. 创建到MySQL的数据库连接…...
【数学建模】【2024年】【第40届】【MCM/ICM】【E题 财产保险的可持续性】【解题思路】
一、题目 (一) 赛题原文 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版本,可能有莫名其妙的错误,这里使用的是springboot-2.6.13,springcloud-2021.0.5 一,Eureka-Server搭建: 1.创建项目:引入依赖 <dependency><groupId>org.sp…...
ansible shell模块 可以用来使用shell 命令 支持管道符 shell 模块和 command 模块的区别
这里写目录标题 说明shell模块用法shell 模块和 command 模块的区别 说明 shell模块可以在远程主机上调用shell解释器运行命令,支持shell的各种功能,例如管道等 shell模块用法 ansible slave -m shell -a cat /etc/passwd | grep root # 可以使用管道…...
qss的使用
参考:qss样式表笔记大全(二):可设置样式的窗口部件列表(上)(持续更新示例)_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 源,这个可以参考我之前的博客 虚拟机内使用 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下载后解压,配置系统环境变量 > sudo vim /etc/profile添加以下两行 export HADOOP_HOME/Users/collinsliu/…...
机器学习算法之支持向量机(SVM)
SVM恐怕大家即使不熟悉,也听说过这个大名吧,这一节我们就介绍这相爱相杀一段内容。 前言:在介绍一个新内容之SVM前,我们不觉映入眼帘的问题是为什么要引入SVM?吃的香,睡的着的情况下,肯定不会是…...
线性判别分析(LDA)
一、说明 LDA 是一种监督降维和分类技术。其主要目的是查找最能分隔数据集中两个或多个类的特征的线性组合。LDA 的主要目标是找到一个较低维度的子空间,该子空间可以最大限度地区分不同类别,同时保留与歧视相关的信息。 LDA 是受监督的,这意…...
Vue 前置导航
Vue 前置导航(Vue Front Navigation)是一种在 Vue.js 框架中实现导航功能的常见方式。它通常用于构建单页应用程序(Single Page Application),通过在页面顶部或侧边栏显示导航菜单,使用户能够轻松切换到不同…...
【仅限首批内测用户开放】Polars 2.0清洗性能调优白皮书:含12个未公开API、3类CPU亲和性绑定策略
第一章:Polars 2.0大规模数据清洗技巧概览Polars 2.0 在性能、内存效率与API一致性上实现重大升级,为TB级结构化数据清洗提供了低延迟、高吞吐的原生解决方案。其基于Arrow 15的列式引擎、零拷贝切片能力及多线程LazyFrame执行计划优化,使复杂…...
CSS动画播放状态控制终极指南:掌握交互式动画实现技巧
CSS动画播放状态控制终极指南:掌握交互式动画实现技巧 【免费下载链接】css-reference CSS Reference: a free visual guide to the most popular CSS properties 项目地址: https://gitcode.com/gh_mirrors/cs/css-reference CSS动画播放状态控制是网页交互…...
LangFlow小白也能玩转AI:无需代码基础,快速构建智能应用
LangFlow小白也能玩转AI:无需代码基础,快速构建智能应用 1. 什么是LangFlow? LangFlow是一款让普通人也能轻松玩转AI的神奇工具。想象一下,如果你能用拖拽的方式,像搭积木一样构建AI应用,是不是很酷&…...
VideoAgentTrek Screen Filter在运维监控中的应用:自动过滤服务器录屏中的敏感信息
VideoAgentTrek Screen Filter在运维监控中的应用:自动过滤服务器录屏中的敏感信息 想象一下这个场景:你作为运维工程师,刚刚处理完一个棘手的线上故障。为了复盘和分享经验,你需要把整个排查过程的服务器操作录屏发给同事或者上…...
3步快速设置Windows任务栏透明美化:TranslucentTB新手完整指南
3步快速设置Windows任务栏透明美化:TranslucentTB新手完整指南 【免费下载链接】TranslucentTB A lightweight utility that makes the Windows taskbar translucent/transparent. 项目地址: https://gitcode.com/gh_mirrors/tr/TranslucentTB 想要让Windows…...
旧笔记本别扔!用飞牛OS+阿里云DDNS,5分钟搞定个人云盘外网访问
旧笔记本改造指南:用飞牛OS与阿里云DDNS打造高性价比个人云存储 你是否曾为家中堆积的旧电子设备感到困扰?那些性能落后但依然能正常运行的旧笔记本,其实蕴藏着巨大的实用价值。本文将带你探索如何将这些被时代淘汰的硬件变废为宝,…...
03-CAPL 常用函数大全
专栏:《CAPL 脚本编写实战指南》第 3 篇 作者:一线汽车电子测试工程师 适合人群:已掌握 CAPL 基础的测试人员、想系统学习 CAPL 函数的工程师开篇:为什么要学 CAPL 函数? 这是我刚学 CAPL 时的真实经历。 当时的情况&a…...
Waymo Open Dataset Docker部署:环境配置与容器化最佳实践
Waymo Open Dataset Docker部署:环境配置与容器化最佳实践 【免费下载链接】waymo-open-dataset Waymo Open Dataset 项目地址: https://gitcode.com/gh_mirrors/wa/waymo-open-dataset Waymo Open Dataset是自动驾驶领域的重要开源项目,提供了丰…...
保姆级教程:用MQTT.fx客户端连接电信AEP物联网平台,实现设备数据上报与远程控制
从零到一:用MQTT.fx玩转电信AEP物联网平台全流程实战 在物联网开发领域,电信AEP平台作为国内主流物联网云服务平台之一,为开发者提供了从设备接入到数据管理的完整解决方案。而MQTT.fx作为轻量级MQTT客户端工具,因其简洁直观的界面…...
wan2.1-vae镜像特性解析:服务器重启自动恢复服务机制说明
wan2.1-vae镜像特性解析:服务器重启自动恢复服务机制说明 1. 平台核心能力概述 muse/wan2.1-vae是基于Qwen-Image-2512模型的AI图像生成平台,其核心优势在于: 双语言支持:同时兼容中英文提示词输入超高分辨率:最高支…...
