当前位置: 首页 > 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;使用户能够轻松切换到不同…...

SDMatte数据库课程设计案例:电商商品图库智能管理系统

SDMatte数据库课程设计案例&#xff1a;电商商品图库智能管理系统 1. 项目背景与需求分析 电商平台每天需要处理大量商品图片&#xff0c;传统人工修图方式存在效率低、成本高、风格不统一等问题。某服装电商平台希望开发一套智能图库管理系统&#xff0c;能够自动完成商品图…...

从科研到工程:为什么我选择用ROS2重构Apollo/autoware的规控算法?

从科研到工程&#xff1a;为什么我选择用ROS2重构Apollo/autoware的规控算法&#xff1f; 在自动驾驶领域&#xff0c;从实验室原型到量产系统的跨越&#xff0c;往往伴随着技术栈的全面升级。三年前&#xff0c;当我第一次将Apollo的规划控制模块移植到ROS1环境时&#xff0c;…...

我的世界Waterfall跨服配置避坑指南:从‘连接被拒绝’到流畅穿梭的完整排错流程

我的世界Waterfall跨服配置避坑指南&#xff1a;从‘连接被拒绝’到流畅穿梭的完整排错流程 当你兴奋地搭建好Waterfall跨服架构&#xff0c;却在测试时遭遇"连接被拒绝"的红色提示&#xff0c;或是玩家卡在大厅无法切换子服时&#xff0c;那种挫败感我深有体会。本文…...

Clover Bootloader虚拟化环境部署终极指南:QEMU、KVM、Xen全平台支持

Clover Bootloader虚拟化环境部署终极指南&#xff1a;QEMU、KVM、Xen全平台支持 【免费下载链接】CloverBootloader Bootloader for macOS, Windows and Linux in UEFI and in legacy mode 项目地址: https://gitcode.com/gh_mirrors/cl/CloverBootloader Clover Bootl…...

网络异常排查:快速定位域连接问题

问题描述与初步排查网络位置异常通常表现为计算机无法正确识别当前所在的AD域环境&#xff0c;导致访问域资源受限或登录问题。常见症状包括系统托盘显示“无法访问域”、组策略无法应用、DNS解析失败等。检查计算机是否能够ping通域控制器的主机名和IP地址。使用nslookup命令验…...

MediaPipeUnityPlugin技术解构与实战指南:Unity AI视觉开发进阶之路

MediaPipeUnityPlugin技术解构与实战指南&#xff1a;Unity AI视觉开发进阶之路 【免费下载链接】MediaPipeUnityPlugin Unity plugin to run MediaPipe 项目地址: https://gitcode.com/gh_mirrors/me/MediaPipeUnityPlugin 问题发现&#xff1a;Unity AI视觉开发的现实…...

UEFI启动画面定制指南:3步实现个性化Windows启动界面

UEFI启动画面定制指南&#xff1a;3步实现个性化Windows启动界面 【免费下载链接】HackBGRT Windows boot logo changer for UEFI systems 项目地址: https://gitcode.com/gh_mirrors/ha/HackBGRT HackBGRT是一款专为UEFI系统设计的Windows启动画面定制工具&#xff0c;…...

【TC3xx芯片】Endinit机制实战:从解锁到上锁的完整代码解析

1. TC3xx芯片Endinit机制的核心作用 在嵌入式系统开发中&#xff0c;寄存器保护是确保系统稳定性的关键机制。TC3xx系列芯片采用的Endinit&#xff08;End of initialization&#xff09;保护方案&#xff0c;就像给重要寄存器装了一把智能密码锁。想象一下&#xff0c;你家的保…...

终极视频硬字幕提取指南:本地OCR识别87种语言的完整解决方案

终极视频硬字幕提取指南&#xff1a;本地OCR识别87种语言的完整解决方案 【免费下载链接】video-subtitle-extractor 视频硬字幕提取&#xff0c;生成srt文件。无需申请第三方API&#xff0c;本地实现文本识别。基于深度学习的视频字幕提取框架&#xff0c;包含字幕区域检测、字…...

Nunchaku FLUX.1-dev 文生图技术解析:卷积神经网络在图像生成中的角色

Nunchaku FLUX.1-dev 文生图技术解析&#xff1a;卷积神经网络在图像生成中的角色 最近在尝试各种文生图模型时&#xff0c;Nunchaku FLUX.1-dev 的表现让我印象深刻。它生成的图片不仅细节丰富&#xff0c;而且风格多样&#xff0c;从写实到抽象都能驾驭得很好。这让我不禁好…...