Day95 | 灵神 | 二叉树 二叉树的垂序遍历

987.二叉树的垂序遍历

987. 二叉树的垂序遍历 - 力扣（LeetCode）

思路：

这道题是个hard题，emm感觉是个mid题

首先这道题难点不在递归，因为递归完成的任务只是标记每个节点的row和col而已

难在对数据的处理，其实也不难，就是把所有顶点的值记录到三元组里面

第一个元素col，第二个元素row，第三个元素节点的值，按照这三个元素排序就行

按照第一个元素大小排，一样的话看第二个，还一样的话看第三个，最后输出出来就行

完整代码：

笔者用的是map<int,vector<pair<int,int>>>

第一个元素大小的排序在插入map时已经完成，因为map底层是红黑树

那就只需要对col相同的vector<pair<int,int>>排序就好了，直接使用sort

sort排序pair就是先看第一个元素大小，一样的话看第二个元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    map<int,vector<pair<int,int>>> p;
    void tra(TreeNode *t,int row,int col)
    {
        if(t==nullptr)
            return ;
        p[col].emplace_back(row,t->val);
        tra(t->left,row+1,col-1);
        tra(t->right,row+1,col+1);
    }
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        tra(root,0,0);
        vector<vector<int>> res;
        for(auto c:p)
        {
            //排列第二个第三个元素大小
            ranges::sort(c.second);
            vector<int> path;
            for(auto s:c.second)
                path.push_back(s.second);
            res.push_back(path);
        }
        return res;
    }
};

灵神代码（四个写法，我只贴了写法一）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    map<int, vector<pair<int, int>>> groups;

    void dfs(TreeNode *node, int row, int col) {
        if (node == nullptr) {
            return;
        }
        // col 相同的分到同一组
        groups[col].emplace_back(row, node->val);
        dfs(node->left, row + 1, col - 1);
        dfs(node->right, row + 1, col + 1);
    }

public:
    vector<vector<int>> verticalTraversal(TreeNode *root) {
        dfs(root, 0, 0);
        vector<vector<int>> ans;
        for (auto &[_, g] : groups) {
            ranges::sort(g);
            vector<int> vals;
            for (auto &[_, val] : g) {
                vals.push_back(val);
            }
            ans.push_back(vals);
        }
        return ans;
    }
};