搜索+哈希/平衡树,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),通过在页面顶部或侧边栏显示导航菜单,使用户能够轻松切换到不同…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
React Native 导航系统实战(React Navigation)
导航系统实战(React Navigation) React Navigation 是 React Native 应用中最常用的导航库之一,它提供了多种导航模式,如堆栈导航(Stack Navigator)、标签导航(Tab Navigator)和抽屉…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
AI Agent与Agentic AI:原理、应用、挑战与未来展望
文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例:使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例:使用OpenAI GPT-3进…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
使用 SymPy 进行向量和矩阵的高级操作
在科学计算和工程领域,向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能,能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作,并通过具体…...
