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.二叉树的垂序遍历:遍历时存节点信息,遍历完自定义排序 力扣题目链接:https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/ 给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历…...
TCP 和 UDP的区别
文章目录 概述区别UDPTCPTCP与UDP的选择UDP和TCP编程区别 概述 TCP(Transmission Control Protocol,传输控制协议)和 UDP(User Datagram Protocol,用户数据报协议)是互联网中两种最常用的传输层协议 总的来…...
Python 将一维数组或矩阵变为三维
Python 将一维数组或矩阵变为三维 正文 正文 话不多说直接上代码: 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消息
因为生活中老是忘记各种事情,刚好又在学python,便突发奇想通过python实现提醒任务的功能(尽管TIM有定时功能),也可定时给好友、群、讨论组发送qq消息。其工作流程是:访问数据库提取最近计划——>根据数据…...
支付方式接入:支付宝、微信支付、微软支付
支付方式接入:支付宝、微信支付、微软支付 1、微信支付-接入指引 2、支付宝-接入指引 3、微软支付-接入指引 3.1、使用visual studio打包应用(发布到微软市场):Package a desktop app from source code using Visual Studio -…...
C++中的互斥量
互斥量是一个类,互斥量的使用必须引入头文件#include <mutex>。互斥量就如同一把锁,在同一时间,多个线程都可以调用lock成员函数尝试给这把锁头加锁,但是只有一个线程可以成功给这把锁加锁,其他没有加锁成功的线…...
盲盒小程序开发
现如今,盲盒已经成为了市场上不可忽视的新型消费模式,并且也逐渐遍布在全球各地中。盲盒的种类商品也逐渐丰富完善,不在局限于性价比高的盲盒玩具、手办等,也发展到了美妆、电子、食品等行业,具有较大的实用性和收藏价…...
安装 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版本 第一步,先查看本机node.js版本: node -v 第二步,清除node.js的cache: sudo npm cache clean -f 第三步,安装 n 工具,这个工具是专门用来管理node.js版本的,别怀疑这个工具…...
Python爬虫之Splash详解
爬虫专栏:http://t.csdnimg.cn/WfCSx Splash 的使用 Splash 是一个 JavaScript 渲染服务,是一个带有 HTTP API 的轻量级浏览器,同时它对接了 Python 中的 Twisted 和 QT 库。利用它,我们同样可以实现动态渲染页面的抓取。 1. 功…...
Deep深度系统下载安装Beyond compare4
Beyond Compare 4下载和安装 1、在线安装 Debian, Ubuntu安装命令: 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 脚本
需求: 利用QScintilla 编辑lua 脚本 步骤: 1,下载 QScintilla Riverbank Computing | Download 2, 打开 src/qscintilla.pro 文件 编译出 dll库 3,工程中引入这个库 注意debug 模式 必须加载debug 版本编译的库࿰…...
2022长安杯复现
案件情况 某地警方接到受害人报案称其在某虚拟币交易网站遭遇诈骗,该网站号称使用“USTD 币”购买所谓的“HT 币”,受害人充 值后不但“HT 币”无法提现、交易,而且手机还被恶意软件锁定 勒索。警方根据受害人提供的虚拟币交易网站调取了对应…...
Netty Review - NioEventLoopGroup源码解析
文章目录 概述类继承关系源码分析小结 概述 EventLoopGroup bossGroup new NioEventLoopGroup(1); EventLoopGroup workerGroup new NioEventLoopGroup();这段代码是在使用Netty框架时常见的用法,用于创建两个不同的EventLoopGroup实例,一个用于处理连…...
团队配置管理规范浅见
在一段时间的工作过程中配置管理工作确实对我们的生产活动产生了巨大的工作量,现在就这个工作来进行梳理一下。 本文主要分为两部分: 1、借用软件系统分析师的配置管理部分内容来介绍配置管理的工作(原谅时间精力有限,原文基本已…...
「算法」二分查找1:理论细节
🎇个人主页:Ice_Sugar_7 🎇所属专栏:算法详解 🎇欢迎点赞收藏加关注哦! 二分查找算法简介 这个算法的特点就是:细节多,出错率高,很容易就写成死循环有模板,但…...
【网络安全】什么样的人适合学?该怎么学?
有很多想要转行网络安全或者选择网络安全专业的人在进行决定之前一定会有的问题: 什么样的人适合学习网络安全?我适不适合学习网络安全? 当然,产生这样的疑惑并不奇怪,毕竟网络安全这个专业在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协议:规定了浏览器发送及服务器返回内容的格式 请求报文:浏览器按照HTTP协议要求的格式,发送给服务器的内容 1.1 请求报文的格式 请求报文的组成部分有: 请求行:请求方法,URL…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
