314. Binary Tree Vertical Order Traversal ---M

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]
]

A:
Leetcode自己的定义是这样的：
每个node，假设horizontal index 是 a， 则node.left的宽坐标是a-1,  node.right 的宽坐标是a+1
核心就是，先搞成map index to result, 最后再连起来

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> verticalOrder(TreeNode* root) {        
        unordered_map<int, vector<int>> M;
        helper(root, 0, M);// return the left most edge. Root is 0,root->left is -1
        vector<vector<int>> res;
        for(int key = leftMost; M.find(key)!=M.end();key++)
            res.push_back(M[key]);
        return res;
    }
private:
    int leftMost=0;
    void helper(TreeNode* root, int cur,unordered_map<int, vector<int>> & M){
        if(not root)
            return;
        leftMost = min(leftMost, cur);
        M[cur].push_back(root->val);
        helper(root->left, cur-1, M);
        helper(root->right,cur+1, M);
    }
};

然而，有个case 总是过不了。 

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

很奇怪，可是本地是对的

Mistakes:
1: 当把L的最后一行和root对比想联的生活。   忘记，要先root，再Left，再Right