变式一：二叉树的垂直序遍历 (Vertical Order Traversal)

题目：给定一个二叉树，返回其节点的垂直序遍历。即，从左到右依次返回每一列的节点，同一列内的节点从上到下排列。

例子：

  3
 / \
9   20
   /  \
  15   7

垂直序遍历的结果是：[[9], [3, 15], [20], [7]]

const verticalOrder = (root) =>{
    if(!root) return [];

    // 构建一个索引即可;

    // Map: { columnVal -> [node.val, node.val, ...] }
    // 
    let columnMap = new Map();
    // Queue: [node, column_index]
    let level = [[root, 0]];
    let minColVal = 0, maxColVal = 0;

    while(level.length >0){
        const [node, colVal] = level.shift();

        if(!columnMap.has(colVal)){
            columnMap.set(colVal, []);
        }

        columnMap.get(colVal).push(node.val);

        minColVal = Math.min(minColVal, colVal);
        maxColVal = Math.max(maxColVal, colVal);

        if(node.left){
            level.push([node.left, colVal-1]);
        }
        if(node.right){
            level.push([node.right, colVal+1])
        }
    }

    const ans = [];
    // 注意这里要遍历到maxColVal才行；
    for(let i=minColVal;i<maxColVal+1;i++){
        ans.push(columnMap.get(i))
    }

    return ans;
}