314-二叉树的垂直遍历

LeetCode 314. 二叉树的垂直遍历

给你一个二叉树的根结点，返回其结点按 垂直方向（从上到下，逐列）遍历的结果。

如果两个结点在同一行和列，那么顺序则为 从左到右。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]

method

按层序遍历的方式，往左就列数-1，往右就列数+1，并用哈希表存储每列的值

vector<vector<int>> verticalOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    map<int, vector<int>> mp;
    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto [node, col] = q.front();
            q.pop();
            mp[col].push_back(node->val);
            if (node->left) q.push({node->left, col - 1});
            if (node->right) q.push({node->right, col + 1});
        }
    }
    for (auto m : mp) {
        res.push_back(m.second);
    }
    return res;
}

---

LeetCode 987. 二叉树的垂序遍历

给你二叉树的根结点 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 在此列中。

method

map<int, multiset<pair<int, int>>> mp;  // multiset可以自动排序
vector<vector<int>> verticalTraversal(TreeNode* root) {
    queue<pair<TreeNode*, int>> q;
    q.push({root, 0});
    int depth = 0;
    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto [node, col] = q.front();
            q.pop();
            mp[col].insert({depth, node->val});
            if (node->left) q.push({node->left, col - 1});
            if (node->right) q.push({node->right, col + 1});
        }
        depth += 1;
    }
    vector<vector<int>> res;
    for (auto m : mp) { // m --> multiset
        vector<int> tmp;
        for (auto n : m.second) {   // n --> pair<int,int>
            tmp.push_back(n.second);    // 把节点值取出来
        }
        res.push_back(tmp);
    }
    return res;
}