314. Binary Tree Vertical Order Traversal (Medium)

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. Given binary tree [3,9,20,null,null,15,7],

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

   return its vertical order traversal as:

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

2. Given binary tree [3,9,8,4,0,1,7],

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

   return its vertical order traversal as:

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

3. Given binary tree [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
   

   return its vertical order traversal as:

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

Solution: Level Traverse, Hash Table

这道题让我们竖直遍历二叉树，并把每一列存入一个二维数组，我们看题目中给的第一个例子，3和15属于同一列，3在前，第二个例子中，3,5,2在同一列，3在前，5和2紧随其后，那么我们隐约的可以感觉到好像是一种层序遍历的前后顺序，那么我们如何来确定列的顺序呢，我们可以把根节点给个序号0，然后开始层序遍历，凡是左子节点则序号减1，右子节点序号加1，这样我们可以通过序号来把相同列的节点值放到一起，我们用一个map来建立序号和其对应的节点值的映射，用map的另一个好处是其自动排序功能可以让我们的列从左到右，由于层序遍历需要用到queue，我们此时queue里不能只存节点，而是要存序号和节点组成的pair，这样我们每次取出就可以操作序号，而且排入队中的节点也赋上其正确的序号，代码如下：

/**
 * 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) {
        vector<vector<int>> res;
        if (!root) return res;
        queue<pair<int,TreeNode*>> q;
        map<int, vector<int>> m;
        q.push({0, root});
        while (!q.empty()) {
            int id = q.front().first;
            TreeNode* node = q.front().second; q.pop();
            m[id].push_back(node->val);
            if (node->left) q.push({id-1, node->left});
            if (node->right) q.push({id+1, node->right});
        }

        for (auto& a: m) res.push_back(a.second);

        return res;
    }
};