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

LeetCode 0987.二叉树的垂序遍历:遍历时存节点信息,遍历完自定义排序

【LetMeFly】987.二叉树的垂序遍历:遍历时存节点信息,遍历完自定义排序

力扣题目链接:https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/

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

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

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

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

 

示例 1:

输入:root = [3,9,20,null,null,15,7]
输出:[[9],[3,15],[20],[7]]
解释:
列 -1 :只有结点 9 在此列中。
列  0 :只有结点 3 和 15 在此列中,按从上到下顺序。
列  1 :只有结点 20 在此列中。
列  2 :只有结点 7 在此列中。

示例 2:

输入:root = [1,2,3,4,5,6,7]
输出:[[4],[2],[1,5,6],[3],[7]]
解释:
列 -2 :只有结点 4 在此列中。
列 -1 :只有结点 2 在此列中。
列  0 :结点 1 、5 和 6 都在此列中。1 在上面,所以它出现在前面。5 和 6 位置都是 (2, 0) ,所以按值从小到大排序,5 在 6 的前面。
列  1 :只有结点 3 在此列中。
列  2 :只有结点 7 在此列中。

示例 3:

输入:root = [1,2,3,4,6,5,7]
输出:[[4],[2],[1,5,6],[3],[7]]
解释:
这个示例实际上与示例 2 完全相同,只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同,所以答案保持不变,仍然按值从小到大排序。

 

提示:

  • 树中结点数目总数在范围 [1, 1000]
  • 0 <= Node.val <= 1000

方法一:遍历时存节点信息,遍历完自定义排序(以广度优先搜索为例)

广度优先搜索(BFS)相信大家都不陌生,因此我们可以二话不说将二叉树广搜一遍,在搜索过程中将所需要的信息计算并存下来,剩下的就是按照题目规则自定义排序了。

都需要哪些信息呢?需要“节点在哪一列”、“节点深度”、“节点值”。

遍历过程中将上述三元组存下来,遍历完成后依据这三个信息排序,作为答案并返回即可。

  • 时间复杂度 O ( N log ⁡ N ) O(N\log N) O(NlogN),其中 N N N是二叉树中节点的个数
  • 空间复杂度 O ( N ) O(N) O(N)

AC代码

C++
class Solution {
public:vector<vector<int>> verticalTraversal(TreeNode* root) {queue<NodeInfo> q;  // [<node, <col, height>>, ...q.push({root, {0, 1}});vector<NodeInfo> v;while (q.size()) {NodeInfo thisNode = q.front();q.pop();v.push_back(thisNode);if (thisNode.first->left) {q.push({thisNode.first->left, {thisNode.second.first - 1, thisNode.second.second + 1}});}if (thisNode.first->right) {q.push({thisNode.first->right, {thisNode.second.first + 1, thisNode.second.second + 1}});}}sort(v.begin(), v.end(), [&](const NodeInfo& a, const NodeInfo& b) {return a.second == b.second ? a.first->val < b.first->val : a.second < b.second;});vector<vector<int>> ans;int lastCol = 1000000;for (NodeInfo& a : v) {if (a.second.first != lastCol) {lastCol = a.second.first;ans.push_back({});}ans.back().push_back(a.first->val);}return ans;}
};
Python
# from typing import List# # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = rightclass Solution:def verticalTraversal(self, root: TreeNode) -> List[List[int]]:q = [(0, 0, root)]  # [(col, depth, node), ...v = []  # [(col, depth, val), ...]while q:thisCol, thisDepth, thisNode = q.pop()  # actually is't queue but a stackv.append((thisCol, thisDepth, thisNode.val))if thisNode.left:q.append((thisCol - 1, thisDepth + 1, thisNode.left))if thisNode.right:q.append((thisCol + 1, thisDepth + 1, thisNode.right))v.sort()ans = []lastCol = 100000for col, _, val in v:if col != lastCol:lastCol = colans.append([])ans[-1].append(val)return ans

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/136106019

相关文章:

LeetCode 0987.二叉树的垂序遍历:遍历时存节点信息,遍历完自定义排序

【LetMeFly】987.二叉树的垂序遍历&#xff1a;遍历时存节点信息&#xff0c;遍历完自定义排序 力扣题目链接&#xff1a;https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/ 给你二叉树的根结点 root &#xff0c;请你设计算法计算二叉树的 垂序遍历…...

TCP 和 UDP的区别

文章目录 概述区别UDPTCPTCP与UDP的选择UDP和TCP编程区别 概述 TCP&#xff08;Transmission Control Protocol&#xff0c;传输控制协议&#xff09;和 UDP&#xff08;User Datagram Protocol&#xff0c;用户数据报协议&#xff09;是互联网中两种最常用的传输层协议 总的来…...

Python 将一维数组或矩阵变为三维

Python 将一维数组或矩阵变为三维 正文 正文 话不多说直接上代码&#xff1a; import numpy as npsampling_points 10001arr np.linspace(0, 2, sampling_points) arr_3D arr.reshape(1, 1, -1) print(arr_3D) """ result: [[[0.0000e00 2.0000e-04 4.0000…...

Python如何实现定时发送qq消息

因为生活中老是忘记各种事情&#xff0c;刚好又在学python&#xff0c;便突发奇想通过python实现提醒任务的功能&#xff08;尽管TIM有定时功能&#xff09;&#xff0c;也可定时给好友、群、讨论组发送qq消息。其工作流程是&#xff1a;访问数据库提取最近计划——>根据数据…...

支付方式接入:支付宝、微信支付、微软支付

支付方式接入&#xff1a;支付宝、微信支付、微软支付 1、微信支付-接入指引 2、支付宝-接入指引 3、微软支付-接入指引 3.1、使用visual studio打包应用&#xff08;发布到微软市场&#xff09;&#xff1a;Package a desktop app from source code using Visual Studio -…...

C++中的互斥量

互斥量是一个类&#xff0c;互斥量的使用必须引入头文件#include <mutex>。互斥量就如同一把锁&#xff0c;在同一时间&#xff0c;多个线程都可以调用lock成员函数尝试给这把锁头加锁&#xff0c;但是只有一个线程可以成功给这把锁加锁&#xff0c;其他没有加锁成功的线…...

盲盒小程序开发

现如今&#xff0c;盲盒已经成为了市场上不可忽视的新型消费模式&#xff0c;并且也逐渐遍布在全球各地中。盲盒的种类商品也逐渐丰富完善&#xff0c;不在局限于性价比高的盲盒玩具、手办等&#xff0c;也发展到了美妆、电子、食品等行业&#xff0c;具有较大的实用性和收藏价…...

安装 Windows 10

1.镜像安装 镜像安装:安装Windows 10 2.安装过程(直接以图的形式呈现) 选择专业版的 等待安装即可...

C++文件操作->文本文件(->写文件、读文件)、二进制文件(->写文件、读文件)

#include<iostream> using namespace std; #include <fstream>//头文件包含 //文本文件 写文件 void test01() { //1.包含头文件 fstream //2.创建流对象 ofstream ofs; //3.指定打开方式 ofs.open("test.txt", ios::out); //4.写…...

Mac相关问题

Mac 更新node版本 第一步&#xff0c;先查看本机node.js版本&#xff1a; node -v 第二步&#xff0c;清除node.js的cache&#xff1a; sudo npm cache clean -f 第三步&#xff0c;安装 n 工具&#xff0c;这个工具是专门用来管理node.js版本的&#xff0c;别怀疑这个工具…...

Python爬虫之Splash详解

爬虫专栏&#xff1a;http://t.csdnimg.cn/WfCSx Splash 的使用 Splash 是一个 JavaScript 渲染服务&#xff0c;是一个带有 HTTP API 的轻量级浏览器&#xff0c;同时它对接了 Python 中的 Twisted 和 QT 库。利用它&#xff0c;我们同样可以实现动态渲染页面的抓取。 1. 功…...

Deep深度系统下载安装Beyond compare4

Beyond Compare 4下载和安装 1、在线安装 Debian, Ubuntu安装命令&#xff1a; wget https://www.scootersoftware.com/bcompare-4.4.6.27483_amd64.deb sudo apt update sudo apt install ./bcompare-4.4.6.27483_amd64.deb Redhat Enterprise Linux, Fedora, CentOS安装命令…...

Qt 使用QScintilla 编辑lua 脚本

需求&#xff1a; 利用QScintilla 编辑lua 脚本 步骤&#xff1a; 1&#xff0c;下载 QScintilla Riverbank Computing | Download 2, 打开 src/qscintilla.pro 文件 编译出 dll库 3&#xff0c;工程中引入这个库 注意debug 模式 必须加载debug 版本编译的库&#xff0…...

2022长安杯复现

案件情况 某地警方接到受害人报案称其在某虚拟币交易网站遭遇诈骗&#xff0c;该网站号称使用“USTD 币”购买所谓的“HT 币”&#xff0c;受害人充 值后不但“HT 币”无法提现、交易&#xff0c;而且手机还被恶意软件锁定 勒索。警方根据受害人提供的虚拟币交易网站调取了对应…...

Netty Review - NioEventLoopGroup源码解析

文章目录 概述类继承关系源码分析小结 概述 EventLoopGroup bossGroup new NioEventLoopGroup(1); EventLoopGroup workerGroup new NioEventLoopGroup();这段代码是在使用Netty框架时常见的用法&#xff0c;用于创建两个不同的EventLoopGroup实例&#xff0c;一个用于处理连…...

团队配置管理规范浅见

在一段时间的工作过程中配置管理工作确实对我们的生产活动产生了巨大的工作量&#xff0c;现在就这个工作来进行梳理一下。 本文主要分为两部分&#xff1a; 1、借用软件系统分析师的配置管理部分内容来介绍配置管理的工作&#xff08;原谅时间精力有限&#xff0c;原文基本已…...

「算法」二分查找1:理论细节

&#x1f387;个人主页&#xff1a;Ice_Sugar_7 &#x1f387;所属专栏&#xff1a;算法详解 &#x1f387;欢迎点赞收藏加关注哦&#xff01; 二分查找算法简介 这个算法的特点就是&#xff1a;细节多&#xff0c;出错率高&#xff0c;很容易就写成死循环有模板&#xff0c;但…...

【网络安全】什么样的人适合学?该怎么学?

有很多想要转行网络安全或者选择网络安全专业的人在进行决定之前一定会有的问题&#xff1a; 什么样的人适合学习网络安全&#xff1f;我适不适合学习网络安全&#xff1f; 当然&#xff0c;产生这样的疑惑并不奇怪&#xff0c;毕竟网络安全这个专业在2017年才调整为国家一级…...

从零开始学习数据结构—【链表】—【探索环形链的设计之美】

环形链表 文章目录 环形链表1.结构图2.具体实现2.1.环形链表结构2.2.头部添加数据2.2.1.具体实现2.2.2.测试添加数据 2.3.尾部添加数据2.3.1.具体实现2.3.2.添加测试数据 2.4.删除头部数据2.4.1.具体实现2.4.2.测试删除数据 2.5.删除尾部数据2.5.1.具体实现2.5.2.测试删除数据 …...

AJAX——HTTP协议

1 HTTP协议-请求报文 HTTP协议&#xff1a;规定了浏览器发送及服务器返回内容的格式 请求报文&#xff1a;浏览器按照HTTP协议要求的格式&#xff0c;发送给服务器的内容 1.1 请求报文的格式 请求报文的组成部分有&#xff1a; 请求行&#xff1a;请求方法&#xff0c;URL…...

SciencePlots——绘制论文中的图片

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

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...