題目： LeetCode - 987. Vertical Order Traversal of a Binary Tree

題目說明

給一個 Binary Tree，將 Tree 加上虛擬座標，root 為 (0, 0)，左邊節點為 (x - 1, y - 1)，右邊節點為 (x + 1, y - 1)。求從 x 的最小值到 x 的最大值中的元素。( 相同 x 的放在一起，若 x 相同則 y 較小的在前面，若 x、y 都相同則按照數值大小排序 )

解題思路

為了方便排序所以將 y 軸反轉，使用 map<pair<int, int>, priority_queue<int, vector<int>, greater<int>>> 紀錄資料，由於 map 的特性，會依照 pair 的 first 排序，所以裡面存放 {y, x}，由於 priority_queue 會依照資料的大小排序，所以用來存放數值。接著透過遞迴取得資料最後再存入 Vector 即可。

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root) {
        int min_x = INT_MAX, max_x = INT_MIN;
        map<pair<int, int>, priority_queue<int, vector<int>, greater<int>>> m_;
        extract(root, 0, 0, m_, min_x, max_x);
        vector<vector<int>> v(max_x - min_x + 1);
        for(auto& m : m_)
            while(!m.second.empty())
                v[m.first.second - min_x].emplace_back(m.second.top()), m.second.pop();
        return v;
    }
private:
    void extract(TreeNode* root, int x, int y, map<pair<int, int>, priority_queue<int, vector<int>, greater<int>>>& m_, int& min_x, int& max_x)
    {
        if(!root) return;
        min_x = min(min_x, x);
        max_x = max(max_x, x);
        m_[{y, x}].push(root->val);
        extract(root->left, x - 1, y + 1, m_, min_x, max_x);
        extract(root->right, x + 1, y + 1, m_, min_x, max_x);
    }
};

2020/10/26 Rewrite

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> verticalTraversal(TreeNode* root)
    {
        int min_x = INT_MAX, max_x = INT_MIN;
        map<pair<int, int>, priority_queue<int, vector<int>, greater<int>>> _m;
        
        function<void(TreeNode*, int, int)> traversal = [&](TreeNode* r, int x, int y)
        {
            if (!r) return;
            min_x = min(x, min_x);
            max_x = max(x, max_x);
            _m[{y, x}].push(r->val);
            traversal(r->left, x - 1, y + 1);
            traversal(r->right, x + 1, y + 1);
        };
        
        traversal(root, 0, 0);
        vector<vector<int>> v(max_x - min_x + 1);
        for (auto& [pos, pq] : _m) while (!pq.empty()) v[pos.second - min_x].emplace_back(pq.top()), pq.pop();
        return v;
    }
};