LeetCode 987. 二叉树的垂序遍历（递归/循环）-白红宇的个人博客

LeetCode 987. 二叉树的垂序遍历（递归/循环）

发布日期：2021-07-01 03:23:47 浏览次数：2 分类：技术文章

本文共 2591 字，大约阅读时间需要 8 分钟。

1. 题目

给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。

示例 1：

输入：[3,9,20,null,null,15,7]输出：[[9],[3,15],[20],[7]]解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)：然后，值为 9 的结点出现在 (-1, -1)；值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)；值为 20 的结点出现在 (1, -1)；值为 7 的结点出现在 (2, -2)。

示例 2：

输入：[1,2,3,4,5,6,7]输出：[[4],[2],[1,5,6],[3],[7]]解释：根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。 提示：树的结点数介于 1 和 1000 之间。每个结点值介于 0 和 1000 之间。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

map的key记录x坐标，value记录点的集合{val, 深度}

对x一样的点集，按深度第一，值第二进行排序

2.1 递归

class Solution {
   	    map

>> m;//x坐标，节点集合<

>public: vector

> verticalTraversal(TreeNode* root) {

//前序遍历根左右 if(!root) return {

}; dfs(root,0,0); vector

> temp; vector

> ans(m.size()); int i = 0, j; for(auto it = m.begin(); it != m.end(); ++it) { temp = it->second;//点集合 sort(temp.begin(), temp.end(),[&](auto a, auto b){ if(a[1] == b[1]) return a[0] < b[0];//深度一样，按值 return a[1] < b[1];//深度小的在前 }); for(j = 0; j < temp.size(); ++j) ans[i].push_back(temp[j][0]);//数值写入答案 i++; } return ans; } void dfs(TreeNode* root, int x, int deep) { if(!root) return; m[x].push_back({ root->val,deep}); dfs(root->left, x-1, deep+1); dfs(root->right, x+1, deep+1); }};

24 ms 16.3 MB

2.2 层序遍历

class Solution {
   public:    vector
   
    
     > verticalTraversal(TreeNode* root) {
           map

>> m;//x坐标，节点集合<

> if(!root) return {

}; queue

>> q;//节点及其坐标x,y q.push({ root,{ 0,0}}); pair

> tp; TreeNode* node; int x, y; while(!q.empty()) { tp = q.front(); q.pop(); node = tp.first; x = tp.second.first; y = tp.second.second; m[x].push_back(vector

{ node->val,y}); if(node->left) q.push({ node->left, { x-1,y+1}}); if(node->right) q.push({ node->right, { x+1,y+1}}); } vector

> temp; vector

> ans(m.size()); int i = 0, j; for(auto it = m.begin(); it != m.end(); ++it) { temp = it->second; sort(temp.begin(), temp.end(),[&](auto a, auto b){ if(a[1] == b[1]) return a[0] < b[0];//深度一样，按值 return a[1] < b[1];//深度小的在前 }); for(j = 0; j < temp.size(); ++j) ans[i].push_back(temp[j][0]);//数值写入答案 i++; } return ans; }};

16 ms 13.2 MB

转载地址：https://michael.blog.csdn.net/article/details/105681731 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：LeetCode 456. 132模式（逆序遍历+单调栈）

下一篇：LeetCode 916. 单词子集（计数）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！