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…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘
美国西海岸的夏天,再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至,这不仅是开发者的盛宴,更是全球数亿苹果用户翘首以盼的科技春晚。今年,苹果依旧为我们带来了全家桶式的系统更新,包括 iOS 26、iPadOS 26…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
Mysql中select查询语句的执行过程
目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析(Parser) 2.4、执行sql 1. 预处理(Preprocessor) 2. 查询优化器(Optimizer) 3. 执行器…...
AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机
这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机,因为在使用过程中发现 Airsim 对外部监控相机的描述模糊,而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置,最后在源码示例中找到了,所以感…...
若依登录用户名和密码加密
/*** 获取公钥:前端用来密码加密* return*/GetMapping("/getPublicKey")public RSAUtil.RSAKeyPair getPublicKey() {return RSAUtil.rsaKeyPair();}新建RSAUti.Java package com.ruoyi.common.utils;import org.apache.commons.codec.binary.Base64; im…...
