郑州网站设计收费,大型社区网站开发文档,制作公众号的软件,wordpress外贸网站好用的模板下载【LetMeFly】987.二叉树的垂序遍历#xff1a;遍历时存节点信息#xff0c;遍历完自定义排序
力扣题目链接#xff1a;https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree/
给你二叉树的根结点 root #xff0c;请你设计算法计算二叉树的 垂序遍历…【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:vectorvectorint verticalTraversal(TreeNode* root) {queueNodeInfo q; // [node, col, height, ...q.push({root, {0, 1}});vectorNodeInfo 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;});vectorvectorint 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, val0, leftNone, rightNone):
# 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 ist 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原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136106019
