SOURCE

// 从左到右，从上到下遍历二叉树。二叉树的节点的值为整数。
// 1(left 2 right 3)
// 2(left4 right null) 3 (right 5 left null)
// 4(left6 right7) 5(left8 right null)
// 6(left null right null) 7(left null right 9) 8(left 10 right null)
// 9(left null right null) 10(left null right null)

// 上述二叉树的垂直遍历结果为：

// [6,4,2,7,1,9,10,3,8,5]
// 位于相同位置的不同节点的顺序应当继承自其各自的父节点。比如9和10，因为8在7之后，所以10在9之后。

function traverse(root) {
    if (!root) {
        return [];
    };

    const queue = [
        { node: root, position: 0 }
    ];

    const positionMap = new Map();

    while(queue.length > 0) {
        const {node,position} = queue.shift();

        if(!positionMap.has(position)) {
            positionMap.set(position,[]);
        }

        positionMap.get(position).push(node.val);

        if(node.left) {
            queue.push({node:node.left,position:position - 1});
        }
        if(node.right) {
            queue.push ({node:node.right,position:position + 1});
        }
    };

    const sortPosition = Array.from(positionMap.keys()).sort((a,b) => a - b);

    for(let pos of sortPosition) {
        result.push(...positionMap.get(pos));
    };

    return result;
};