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…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
Python 高效图像帧提取与视频编码:实战指南
Python 高效图像帧提取与视频编码:实战指南 在音视频处理领域,图像帧提取与视频编码是基础但极具挑战性的任务。Python 结合强大的第三方库(如 OpenCV、FFmpeg、PyAV),可以高效处理视频流,实现快速帧提取、压缩编码等关键功能。本文将深入介绍如何优化这些流程,提高处理…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
