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

LeetCode二叉树的垂序遍历

题目描述

给你二叉树的根结点 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 在此列中。

987. 二叉树的垂序遍历

解题思路

首先本题是一道困难题,其解决方法并不难想,主要难度主要集中在实现的细节。对于相同列的排序,行小的在前,同行的按照从大到小排序,所以这个实现我想到了java的排序器,制定类的规则。这个问题想好就按照dfs进行一次遍历,主要记录行列,将同列的放入同一个List从而进行排序,整体实现思路并不复杂,主要需要看清楚题意并认真实现。

具体实现,代码如下

class Solution {public List<List<Integer>> verticalTraversal(TreeNode root) {Map<Integer, List<Node>> map = new HashMap<>();List<List<Integer>> lists = new ArrayList<>();List<Integer> list = new ArrayList<>();dfs(0, 0, root, map, list);Collections.sort(list);//进行排序for (int i : list) {Collections.sort(map.get(i));List<Integer> l = new ArrayList<>();for (Node n : map.get(i))l.add(n.val);lists.add(l);}return lists;}public void dfs(int c, int r, TreeNode p, Map<Integer, List<Node>> map, List<Integer> list) {if (p != null) {if (!map.containsKey(c)) {list.add(c);map.put(c, new ArrayList<Node>());}map.get(c).add(new Node(r, p.val));dfs(c - 1, r + 1, p.left, map, list);dfs(c + 1, r + 1, p.right, map, list);}}
}class Node implements Comparable<Node> {int r;int val;Node(int r, int val) {this.r = r;this.val = val;}public int compareTo(Node o) {//排序器if (this.r > o.r) {return 1;} else if (this.r < o.r) {return -1;} else {if (this.val > o.val)return 1;else if (this.val < o.val)return -1;elsereturn 0;}}
}

相关文章:

LeetCode二叉树的垂序遍历

题目描述 给你二叉树的根结点 root &#xff0c;请你设计算法计算二叉树的 垂序遍历 序列。 对位于 (row, col) 的每个结点而言&#xff0c;其左右子结点分别位于 (row 1, col - 1) 和 (row 1, col 1) 。树的根结点位于 (0, 0) 。 二叉树的 垂序遍历 从最左边的列开始直到…...

[linux c]linux do_div() 函数用法

linux do_div() 函数用法 do_div() 是一个 Linux 内核中的宏&#xff0c;用于执行 64 位整数的除法操作&#xff0c;并将结果存储在给定的变量中&#xff0c;同时将余数存储在另一个变量中。这个宏通常用于内核编程中&#xff0c;特别是在处理大整数和性能敏感的场合。 函数原…...

Python学习之路-爬虫提高:常见的反爬手段和解决思路

Python学习之路-爬虫提高:常见的反爬手段和解决思路 常见的反爬手段和解决思路 明确反反爬的主要思路 反反爬的主要思路就是&#xff1a;尽可能的去模拟浏览器&#xff0c;浏览器在如何操作&#xff0c;代码中就如何去实现。浏览器先请求了地址url1&#xff0c;保留了cookie…...

python_numpy库_ndarray的聚合操作、矩阵操作等

一、ndarray的聚合操作 1、求和np.sum() import numpy as np ​ n np.arange(10) print(n) ​ s np.sum(n) print(s) ​ n np.random.randint(0,10,size(3,5)) print(n) s1 np.sum(n) print(s1) #全部数加起来 s2 np.sum(n,axis0) print(s2) #表示每一列的多行求和 …...

python-自动化篇-终极工具-用GUI自动控制键盘和鼠标-pyautogui

文章目录 用GUI自动控制键盘和鼠标pyautogui 模块鼠标屏幕位置——移动地图——pyautogui.size鼠标位置——自身定位——pyautogui.position()移动鼠标——pyautogui.moveTo拖动鼠标滚动鼠标 键盘按下键盘释放键盘 开始与结束通过注销关闭所有程序 用GUI自动控制键盘和鼠标 在…...

面试:大数据和深度学习之间的关系是什么?

大数据与深度学习之间存在着紧密的相互关系&#xff0c;它们在当今技术发展中相辅相成。 大数据的定义与特点:大数据指的是规模(数据量)、多样性(数据类型)和速度(数据生成及处理速度)都超出了传统数据处理软件和硬件能力范围的数据集。它具有四个主要特点&#xff0c;通常被称…...

航芯ACM32G103开发板评测 08 ADC Timer外设测试

航芯ACM32G103开发板评测 08 ADC Timer外设测试 1. 软硬件平台 ACM32G103 Board开发板MDK-ARM Keil 2. 定时器Timer 在一般的MCU芯片中&#xff0c;定时器这个外设资源是非常重要的&#xff0c;一般可以分为SysTick定时器&#xff08;系统滴答定时器&#xff09;、常规定时…...

【Linux学习】生产者-消费者模型

目录 22.1 什么是生产者-消费者模型 22.2 为什么要用生产者-消费者模型? 22.3 生产者-消费者模型的特点 22.4 BlockingQueue实现生产者-消费者模型 22.4.1 实现阻塞队列BlockQueue 1) 添加一个容器来存放数据 2)加入判断Blocking Queue情况的成员函数 3)实现push和pop方法 4)完…...

三、案例 - MySQL数据迁移至ClickHouse

MySQL数据迁移至ClickHouse 一、生成测试数据表和数据1.在MySQL创建数据表和数据2.在ClickHouse创建数据表 二、生成模板文件1.模板文件内容2.模板文件参数详解2.1 全局设置2.2 数据读取&#xff08;Reader&#xff09;2.3 数据写入&#xff08;Writer&#xff09;2.4 性能设置…...

[WinForm开源]概率计算器 - Genshin Impact(V1.0)

创作目的&#xff1a;为方便旅行者估算自己拥有的纠缠之缘能否达到自己的目的&#xff0c;作者使用C#开发了一款小型软件供旅行者参考使用。 创作说明&#xff1a;此软件所涉及到的一切概率与规则完全按照游戏《原神》(V4.4.0)内公示的概率与规则&#xff08;包括保底机制&…...

vscode 代码调试from IPython import embed

一、讲解 这种代码调试方法非常的好用。 from IPython import embed上面的代码片段是用于Python中嵌入一个交互式IPython shell的方法。这可以在任何Python脚本或程序中实现&#xff0c;允许在执行到该点时暂停程序&#xff0c;并提供一个交互式环境&#xff0c;以便于检查、…...

双活工作关于nacos注册中心的数据迁移

最近在做一个双活的项目&#xff0c;在纠结一个注册中心是在双活机房都准备一个&#xff0c;那主机房的数据如果传过去呢&#xff0c;查了一些资料&#xff0c;最终在官网查到了一个NacosSync 的组件&#xff0c;主要用来做数据传输的&#xff0c;并且支持在线替换注册中心的&a…...

5G NR 信道号计算

一、5G NR的频段 增加带宽是增加容量和传输速率最直接的方法&#xff0c;目前5G最大带宽将会达到400MHz&#xff0c;考虑到目前频率占用情况&#xff0c;5G将不得不使用高频进行通信。 3GPP协议定义了从Sub6G(FR1)到毫米波(FR2)的5G目标频谱。 其中FR1是5G的核心频段&#xff0…...

01-Spring实现重试和降级机制

主要用于在模块调用中&#xff0c;出现失败、异常情况下&#xff0c;仍需要进行重复调用。并且在最终调用失败时&#xff0c;可以采用降级措施&#xff0c;返回一般结果。 1、重试机制 我们采用spring 提供的retry 插件&#xff0c;其原理采用aop机制&#xff0c;所以需要额外…...

docker部署showdoc

目录 安装 1.拉取镜像 2.创建容器 使用 1.选择语言 2.默认账户/密码:showdoc/123456​编辑 3.登陆 4.首页 安装 1.拉取镜像 docker pull star7th/showdoc 2.创建容器 mkdir -p /opt/showdoc/html docker run -d --name showdoc --userroot --privilegedtrue -p 1005…...

2.14作业

1.请编程实现二维数组的杨辉三角。 2.请编程实现二维数组计算每一行的和以及列和。 3.请编程实现二维数组计算第二大值。 4.请使用非函数方法实现系统函数strcat,strcmp,strcpy,strlen. strcat: strcmp: strcpy: strlen:...

01.数据结构篇-链表

1.找出两个链表的交点 160. Intersection of Two Linked Lists (Easy) Leetcode / 力扣 例如以下示例中 A 和 B 两个链表相交于 c1&#xff1a; A: a1 → a2↘c1 → c2 → c3↗ B: b1 → b2 → b3 但是不会出现以下相交的情况&#xff0c;因为每个节点只有一个…...

揭秘产品迭代计划制定:从0到1打造完美迭代策略

产品迭代计划是产品团队确保他们能够交付满足客户需求的产品以及实现其业务目标的重要工具。开发一个成功的产品迭代计划需要仔细考虑产品的目标、客户需求、市场趋势和可用资源。以下是帮助您创建产品迭代计划的一些步骤&#xff1a;建立产品目标、收集客户反馈、分析市场趋势…...

Python进阶--下载想要的格言(基于格言网的Python爬虫程序)

注&#xff1a;由于上篇帖子&#xff08;Python进阶--爬取下载人生格言(基于格言网的Python3爬虫)-CSDN博客&#xff09;篇幅长度的限制&#xff0c;此篇帖子对上篇做一个拓展延伸。 目录 一、爬取格言网中想要内容的url 1、找到想要的内容 2、抓包分析&#xff0c;找到想…...

C语言--------数据在内存中的存储

1.整数在内存中的存储 整数在内存是以补码的形式存在的&#xff1b; 整型家族包括char,int ,long long,short类型&#xff1b; 因为char类型是以ASCII值形式存在&#xff0c;所以也是整形家族&#xff1b; 这四种都包括signed,unsigned两种&#xff0c;即有符号和无符号&am…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

Mac flutter环境搭建

一、下载flutter sdk 制作 Android 应用 | Flutter 中文文档 - Flutter 中文开发者网站 - Flutter 1、查看mac电脑处理器选择sdk 2、解压 unzip ~/Downloads/flutter_macos_arm64_3.32.2-stable.zip \ -d ~/development/ 3、添加环境变量 命令行打开配置环境变量文件 ope…...