Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
850 B
1
Indexable
Never
#include <map>
#include <queue>
#include <vector>

using namespace std;

vector<int> verticalOrderTraversal(TreeNode<int>* root) {
    vector<int> ans;
    if (!root) return ans;
    
    map<int, vector<int>> hnodes; 
    queue<pair<TreeNode<int>*, int>> q;
    q.push({root, 0});
    
    while (!q.empty()) {
        auto p = q.front();
        q.pop();
        TreeNode<int>* node = p.first;
        int hd = p.second;
        
        hnodes[hd].push_back(node->data);
        
        if (node->left) q.push({node->left, hd-1});
        if (node->right) q.push({node->right, hd+1});
    }
    
    for (auto it = hnodes.begin(); it != hnodes.end(); it++) {
        vector<int>& nodes = it->second;
        for (int node_val : nodes) {
            ans.push_back(node_val);
        }
    }

    return ans;
}