目录

lc987.二叉树的垂序遍历

Shen 收录于每日一题

2021-07-31 约 481 字预计阅读 1 分钟

目录

987. 二叉树的垂序遍历

利用三元组记录每个节点[列，行，节点值]
之后进行排序，默认的排序方式就是先按列从小到大排序，再按行从小到大排序，最后按节点值排序
这里用到了c++的元组tuple，元组像pair一样。
构造可以使用列表推导的方式进行构造tuple<int, float, int> t = {1, 1.0, 2};
但是元组直接访问元素很复杂，使用std::get<idx>(t);,返回值是引用可以直接修改。
- get的参数必须是编译是的常数(constant)
for each循环可以对tuple直接进行解包，for(const auto& [n1, n2, n3]: rec)
std::tie(n1, n2, n3) = t可以tuple中每个值的引用
c++17标准auto [n1, n2, n3] = t

 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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

typedef pair<int, int> PII;
typedef tuple<int, int, int> TIII;
class Solution {
public:
    vector<TIII> rec;
    void dfs(PII cur, TreeNode* root){
        if(root == nullptr){
            return;
        }
        
        // 列, 行, 节点值
        rec.push_back({cur.second, cur.first, root->val});

        dfs({cur.first + 1, cur.second - 1}, root->left);
        dfs({cur.first + 1, cur.second + 1}, root->right);
    }

    vector<vector<int>> verticalTraversal(TreeNode* root) {
        dfs({0, 0}, root);

        vector< vector<int>> res;
        sort(rec.begin(), rec.end());
        int pre = INT_MIN, idx = -1;
        for(const auto& [col, row, val]: rec){
            if(idx == -1 || pre != col){
                res.push_back({});
                idx += 1;
            }
            res[idx].push_back(val);
            pre = col;
        }

        return res;
    }
};