?LeetCode刷題實(shí)戰(zhàn)314：二叉樹的豎直遍歷

Given a binary tree, return the vertical order traversal of its nodes' values. (ie, from top to bottom, column by column).

If two nodes are in the same row and column, the order should be from left to right.

示例

解題

這道題讓我們豎直遍歷二叉樹，并把每一列存入一個(gè)二維數(shù)組，看題目中給的第一個(gè)例子，3和 15 屬于同一列，3在前，第二個(gè)例子中，3,5,2 在同一列，3在前，5和2緊隨其后，那么隱約的可以感覺到好像是一種層序遍歷的前后順序，如何來確定列的順序呢，這里可以把根節(jié)點(diǎn)給個(gè)序號0，然后開始層序遍歷，凡是左子節(jié)點(diǎn)則序號減1，右子節(jié)點(diǎn)序號加1，這樣可以通過序號來把相同列的節(jié)點(diǎn)值放到一起，用一個(gè) TreeMap 來建立序號和其對應(yīng)的節(jié)點(diǎn)值的映射，用 TreeMap 的另一個(gè)好處是其自動排序功能可以讓列從左到右，由于層序遍歷需要用到 queue，此時(shí) queue 里不能只存節(jié)點(diǎn)，而是要存序號和節(jié)點(diǎn)組成的 pair 對兒，這樣每次取出就可以操作序號，而且排入隊(duì)中的節(jié)點(diǎn)也賦上其正確的序號，代碼如下：

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