Leetcode 314 Solution

This article provides solution to leetcode question 314 (binary-tree-vertical-order-traversal)
Categories:
Tags:
Access this page by simply typing in "lcs 314" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/binary-tree-vertical-order-traversal

Solution

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        map<int, vector<int>> m;

        queue<pair<TreeNode*, int>> q;

        if (root)
            q.push(make_pair(root, 0));

        while (q.empty() == false)
        {
            auto pair = q.front();
            q.pop();

            auto p = pair.first;
            int pos = pair.second;

            m[pos].push_back(p->val);

            if (p->left)
                q.push(make_pair(p->left, pos - 1));

            if (p->right)
                q.push(make_pair(p->right, pos + 1));
        }

        vector<vector<int>> res;
        for (auto pair : m)
            res.push_back(pair.second);
        return res;
    }
};