Print a Binary Tree in Vertical Order

来源：Facebook电面

原帖：http://www.mitbbs.com/article_t/JobHunting/32946511.html
            http://www.geeksforgeeks.org/print-binary-tree-vertical-order-set-2/

题目：

Given a binary tree, print it vertically. The following example illustrates vertical order traversal.

           1
        /    \
       2      3
      / \    / \
     4   5  6   7
             \   \
              8   9 
               
     
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9

思路：这道题dfs + map (因为需要key的顺序保存，所以使用map).或者bfs + map也可。

代码版本使用了bfs + map， 由于dfs不能保证层的顺序。

代码：

 struct TreeNode {  
      int val;  
      TreeNode* left, *right;  
      TreeNode(int v) : val(v), left(NULL), right(NULL) {};  
 };  
   
 vector<vector<int>> verticalPrintBinaryTree(TreeNode* root) {  
      vector<vector<int>> res;  
      if (!root) return res;  
      map<int, vector<int>> table;  
      queue<pair<TreeNode*, int>> q;  
      q.push({root, 0});  
      table[0].push_back(root->val);  
   
       while (!q.empty()) {  
           auto node = q.front().first;  
           int label = q.front().second;  
           q.pop();  
           if (node->left) {  
                table[label-1].push_back(node->left->val);  
                q.push({node->left, label-1});  
           }  
           if (node->right) {  
                table[label+1].push_back(node->right->val);  
                q.push({node->right, label+1});  
           }  
      }  
   
       for (auto it = table.begin(); it != table.end(); ++it) {  
           res.push_back(it->second);  
      }  
      return res;  
 }  
   
 void print(vector<vector<int>>& num) {  
      for (int i = 0; i < num.size(); ++i) {  
           for (int j = 0; j < num[i].size(); ++j) {  
                cout << num[i][j] << " ";  
           }  
           cout << endl;  
      }  
 }  
   
 int main() {  
   TreeNode *root = new TreeNode(1);  
   root->left = new TreeNode(2);  
   root->right = new TreeNode(3);  
   root->left->left = new TreeNode(4);  
   root->left->right = new TreeNode(5);  
   root->right->left = new TreeNode(6);  
   root->right->right = new TreeNode(7);  
   root->right->left->right = new TreeNode(8);  
   root->right->right->right = new TreeNode(9);  
   cout << "Vertical order traversal is \n";  
   vector<vector<int>> res = verticalPrintBinaryTree(root);  
   print(res);  
   return 0;  
 }