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 result = [];
    const queue = [{ node: root, position: 0 }];
    const positionMap = new Map();

    while (queue.length) {
        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;
};

class TreeNode {
    constructor(val, left, right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

const root = new TreeNode(
    1,
    new TreeNode(
        2,
        new TreeNode(4, new TreeNode(6), new TreeNode(7, null, new TreeNode(9))),
        null,
    ),
    new TreeNode(
        3,
        null,
        new TreeNode(5, new TreeNode(8, new TreeNode(10), null), null),
    ),
);

console.log(traverse(root));