987. 二叉树的垂序遍历#

题目#

1
给你二叉树的根结点 root ，
2

3
请你设计算法计算二叉树的 垂序遍历 序列。
4

5
对位于 (row, col) 的每个结点而言，
6

7
其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。
8

9
树的根结点位于 (0, 0) 。
10

11
二叉树的垂序遍历从最左边的列开始直到最右边的列结束，
12

13
按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。
14

15
如果同行同列上有多个结点，则按结点的值从小到大进行排序。
16

17
返回二叉树的 垂序遍历 序列。
18

19
示例 1：
20

21
输入：root = [3,9,20,null,null,15,7]
22
输出：[[9],[3,15],[20],[7]]
23
解释：
24
列 -1 ：只有结点 9 在此列中。
25
列  0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
26
列  1 ：只有结点 20 在此列中。
27
列  2 ：只有结点 7 在此列中。
28

29
示例 2：
30

31
输入：root = [1,2,3,4,5,6,7]
32
输出：[[4],[2],[1,5,6],[3],[7]]
33
解释：
34
列 -2 ：只有结点 4 在此列中。
35
列 -1 ：只有结点 2 在此列中。
36
列  0 ：结点 1 、5 和 6 都在此列中。
37
          1 在上面，所以它出现在前面。
38
          5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
39
列  1 ：只有结点 3 在此列中。
40
列  2 ：只有结点 7 在此列中。
41

42
示例 3：
43

44
输入：root = [1,2,3,4,6,5,7]
45
输出：[[4],[2],[1,5,6],[3],[7]]
46
解释：
47
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
48
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。
49

50
提示：
51

52
树中结点数目总数在范围 [1, 1000] 内
53
0 <= Node.val <= 1000

题目思路#

本质上还是 DFS 与 BFS 的题目，只是解决问题的方式要麻烦一点，所以花费时间较长；本质应属于中等题，算不上难度大的题目；
DFS 采用哈希表加优先队列实现。由于 C++ 的 priority_queue 默认实现为大根堆，而此题需要小根堆，所以使用 multiset（小根堆）实现；
BFS 解法留待考研后再写，现在每天思考题目一个小时，时间上已经太多了。

题目代码#

代码块#

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 *     int val;
5
 *     TreeNode *left;
6
 *     TreeNode *right;
7
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 *     TreeNode(int x, TreeNode *left, TreeNode *right) :
10
        val(x), left(left), right(right) {}
11
 * };
12
 */
13
class Solution {
14
public:
15
    typedef map<int, multiset<pair<int, int>>> maps;
16
    void dfs(TreeNode* root, int x, int y, maps &mp)
17
    {
18
        if(root == nullptr) return;
19
        mp[y].insert({x, root->val});
20
        if(root -> left ) dfs(root -> left, x + 1, y - 1, mp);
21
        if(root -> right) dfs(root -> right, x + 1, y + 1, mp);
22
    }
23
    vector<vector<int>> verticalTraversal(TreeNode* root)
24
    {
25
        maps mp;
26
        dfs(root, 0, 0, mp);
27
        vector<vector<int>> ans;
28
        for(auto & [k, v] : mp)
29
        {
30
            vector<int> vs;
31
            for(auto & p : v) vs.push_back(p.second);
32
            ans.push_back(vs);
33
        }
34
        return ans;
35
    }
36
};

复杂度#

时间复杂度：O(n*logn)
空间复杂度：O(n)