314. Binary Tree Vertical Order Traversal

This is a level order traversal problem. The trick here we need to track index for each node. If root index is i, then left child index is i-1 and right child index is i. Since the output is from left to right, i.e. from smallest index to largest index, we can use map which has sorted the keys. The index is key and the node vector that has this index as value. So the problem becomes level order traversal nodes, compute index for the node and its children, and push the node to right vector mapped by its index.

1:  /**  
2:   * Definition for a binary tree node.  
3:   * struct TreeNode {  
4:   *   int val;  
5:   *   TreeNode *left;  
6:   *   TreeNode *right;  
7:   *   TreeNode(int x) : val(x), left(NULL), right(NULL) {}  
8:   * };  
9:   */  
10:  class Solution {  
11:  public:  
12:    vector<vector<int>> verticalOrder(TreeNode* root) {  
13:      vector<vector<int>> res;  
14:      if (!root) return res;  
15:      map<int, vector<int>> mp;  
16:      queue<pair<int, TreeNode *>> q;  
17:      q.push(make_pair(0, root));  
18:      while (!q.empty()) {  
19:        int sz = q.size();  
20:        for (int i = 0; i < sz; i++) {  
21:          pair<int, TreeNode*> node = q.front();  
22:          q.pop();  
23:          int index = node.first;  
24:          mp[index].push_back(node.second->val);  
25:          if (node.second->left) {  
26:            q.push(make_pair(index-1, node.second->left));  
27:          }  
28:          if (node.second->right) {  
29:            q.push(make_pair(index+1, node.second->right));  
30:          }  
31:        }  
32:      }  
33:      for (auto it : mp) {  
34:        res.push_back(it.second);  
35:      }  
36:      return res;  
37:    }  
38:  };