算法题:二叉树的垂序遍历

描述

给你二叉树的根结点 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

链接:https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree

思路

先遍历树找出输出数组的长度,再次遍历树并保存每个节点的深度和值,将节点插入对应横坐标的列表,最后再排序

代码

class Solution {public:    int m_left, m_right;    vector<vector<int>> verticalTraversal(TreeNode* root) {        getRange(root, 0);        vector<vector<pair<int, int>>> res(m_right-m_left 1, vector<pair<int, int>>());        dfs(root, res, -m_left, 0);        for (auto& list : res) {            sort(list.begin(), list.end(), [](pair<int, int>& a, pair<int, int>& b) -> bool {                if (a.first > b.first) return false;                else if (a.first < b.first) return true;                return a.second < b.second;            });        }        vector<vector<int>> ans;        for (auto & list : res) {            vector<int> temp;            for (auto& p : list) {                temp.push_back(p.second);            }            ans.push_back(temp);        }        return ans;    }    void dfs(TreeNode* root, vector<vector<pair<int, int>>>& res, int i, int depth) {        if (root) {            res[i].push_back({depth, root->val});        }        if (root->left)            dfs(root->left, res, i - 1, depth 1);        if (root->right)            dfs(root->right, res, i   1, depth 1);    }    void getRange(TreeNode* root, int index) {        if (!root) return;        if (m_left > index) m_left = index;        if (m_right < index) m_right = index;        if (root->left) getRange(root->left, index-1);        if (root->right) getRange(root->right, index 1);    }};

复杂度
n 表示节点个数
时间复杂度:O(n)
空间复杂度:O(n)

来源:https://www.icode9.com/content-1-860501.html

(0)

相关推荐

  • ​LeetCode刷题实战144:二叉树的前序遍历

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 图解:什么是并查集?

    Uion-Find 算法 在计算机科学中,并查集(英文:Disjoint-set data structure,直译为不交集数据结构)是一种数据结构,用于处理一些不交集(Disjoint sets,一 ...

  • 岛屿类问题的通用解法、DFS 遍历框架

    在 LeetCode 中,「岛屿问题」是一个系列系列问题,比如: L200. 岛屿数量 (Easy) 463. 岛屿的周长 (Easy) 695. 岛屿的最大面积 (Medium) 827. 最大人工 ...

  • (1条消息) 万字长文!二叉树入门和刷题看这篇就够了!

    今天是小浩算法 "365刷题计划" 二叉树入门 - 整合篇.本篇作为入门整合篇,已经砍去难度较大的知识点,所有列出的内容,均为必须掌握.因为很长,写下目录: 二叉树是啥 二叉树的最 ...

  • ​LeetCode刷题实战404:左叶子之和

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 每日一题 剑指offer(二叉树中和为某一值的路径)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • ​LeetCode刷题实战310:最小高度树

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • ​LeetCode刷题实战145:二叉树的后序遍历

    算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试.所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 ! 今天和大家 ...

  • 算法创作 | 二叉树遍历问题解决方法

    问题描述二叉树的先序遍历.中序遍历.后序遍历怎么求?解决方案给你一个二叉树(如图)那么怎么找出它的先序遍历.中序遍历.后序遍历呢?我们先看一个简单二叉树来了解它的概念. 所谓前序,中序,后序就是指根所 ...

  • 数据结构—树|二叉树|前序遍历、中序遍历、后序遍历【图解实现】

    AI研习图书馆,发现不一样的精彩世界 数据 结构 二叉树的遍历 一.树 在谈二叉树的知识点之前,我们首先来看一下树和图的基本概念. 树:不包含回路的连通无向图,树是一种简单的非线性结构. 由于树有一个 ...

  • 每日一题 剑指offer(二叉搜索树的后序遍历序列)

    编程是很多偏计算机.人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用.因此小白决定开辟一个新的板块"每日一题",通过每天一道编程题目来强化和锻炼自己的编程能力 ...

  • 泰不华《题欧阳修-谱图序稿》欣赏

    元代,泰不华题欧阳修<谱图序稿>,铁血儒帅40岁行楷书,辽宁省博物馆藏. 泰不华(1304-1352),字兼善,伯牙吾台氏,原名达普化,元末诗人.书法家.政治家.元文宗赐名泰不华,至治元年 ...

  • 每日一草:垂序商陆

    一.物种简介 垂序商陆(学名:Phytolacca americana L.),双子叶植物纲,中央种子目,商陆科,商陆属多年生草本植物. 二.物种别名 美国商陆.美商陆.白鸡腿.北美商陆.大麻菜.花商 ...

  • 资源分享—数据结构与算法|图解算法题典【附下载】

    AI研习图书馆,发现不一样的精彩世界 资源 分享 图解算法题典 最近,在学习数据结构的时候,又发现了一个宝藏资源,立马一键三连,回来分享给大家~ 2020年,疫情突如其来,给我们带来了许多困难与挑战. ...

  • 爱因斯坦房子算法题

    有5个人具有5种不同颜色的房间:每个房间住着不同国籍的一个人:每个人都在喝一种特定品牌的饮料:抽一特定品牌的香烟:养某一特定的宠物:没有任意两个人抽相同品牌的烟或喝相同品牌的饮料,或养相同宠物.问:& ...

  • 【枕边算法】回文算法题PHP实现

    ①选择任一数值: ②翻转此数值(例如,选择13则翻转为31),并将原数值和翻转数值相加(13+31): ③相加结果若不是回文,则返回②反复执行,若是回文则终止算法 举例: 13+31=44,44是回文 ...