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.

Examples 1:

Input: [3,9,20,null,null,15,7]

   3
  /\
 /  \
 9  20
    /\
   /  \
  15   7 

Output:

[
  [9],
  [3,15],
  [20],
  [7]
]

Examples 2:

Input: [3,9,8,4,0,1,7]

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7 

Output:

[
  [4],
  [9],
  [3,0,1],
  [8],
  [7]
]

Examples 3:

Input: [3,9,8,4,0,1,7,null,null,null,2,5] (0’s right child is 2 and 1’s left child is 5)

     3
    /\
   /  \
   9   8
  /\  /\
 /  \/  \
 4  01   7
    /\
   /  \
   5   2

Output:

[
  [4],
  [9,5],
  [3,0,1],
  [8,2],
  [7]
]

方法1:

用BFS遍历，并将高度Hd 和 Node * 存入hash table
https://www.youtube.com/watch?v=PQKkr036wRc
易错点：

1. 注意queue里面是pair<int, TreeNode*>, 要用myQueue.front().first 和myQueue.front().second来获取
2. queue的操作：
   queue.front()
queue.back()
queue.push()
queue.emplace() : Construct and insert element
   queue.pop()
queue.swap()
   
   

code

class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (root == nullptr) return result;
        
        map<int, vector<int>> myTable;
        queue<pair<int, TreeNode*>> myQueue;
        
        myQueue.push(make_pair(0, root));
        while (!myQueue.empty()){
            int N = myQueue.size();
            for (int i = 0; i < N; i++){
                int Hd = myQueue.front().first;
                TreeNode* T = myQueue.front().second;
                myQueue.pop();
                
                myTable[Hd].push_back(T->val);
                
                if (T->left != nullptr)
                    myQueue.push(make_pair(Hd - 1, T->left));
                if (T->right != nullptr)
                    myQueue.push(make_pair(Hd + 1, T->right));
            }            
        }
        
        for (auto & v: myTable){
            result.push_back(v.second);
        }
        return result;
    }
};