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…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
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 …...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
