前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >LeetCode 987. 二叉树的垂序遍历

LeetCode 987. 二叉树的垂序遍历

原创
作者头像
freesan44
修改2021-10-08 10:48:47
修改2021-10-08 10:48:47
1900
举报
文章被收录于专栏:freesan44freesan44

题目地址(987. 二叉树的垂序遍历)

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

题目描述

代码语言:txt
复制
给你二叉树的根结点 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

思路

DFS,BFS

关键点

代码

  • 语言支持:Python3

Python3 Code:

代码语言:txt
复制
# 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 = right
class Solution(object):
    def verticalTraversal(self, root):
        seen = collections.defaultdict(
            lambda: collections.defaultdict(list))

        def dfs(root, x=0, y=0):
            if not root:
                return
            seen[x][y].append(root.val)
            dfs(root.left, x-1, y+1)
            dfs(root.right, x+1, y+1)

        dfs(root)
        ans = []
        # x 排序、
        for x in sorted(seen):
            level = []
            # y 排序
            for y in sorted(seen[x]):
                # 值排序
                level += sorted(v for v in seen[x][y])
            ans.append(level)

        return ans

复杂度分析

令 n 为数组长度。

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(n)$

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目地址(987. 二叉树的垂序遍历)
  • 题目描述
  • 思路
  • 关键点
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档