987. Vertical Order Traversal of a Binary Tree

Given the root of a binary tree, calculate the vertical order traversal of the binary tree.

For each node at position (row, col), its left and right children will be at positions (row + 1, col - 1) and (row + 1, col + 1) respectively. The root of the tree is at (0, 0).

The vertical order traversal of a binary tree is a list of top-to-bottom orderings for each column index starting from the leftmost column and ending on the rightmost column. There may be multiple nodes in the same row and same column. In such a case, sort these nodes by their values.

Return the vertical order traversal of the binary tree.

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/

大意：
將每個結點賦(x, y)，x為層級，y為從根結點開始（根結點為零），左子孫-1，右子孫+1的規律，的數字。
將y相同的結點值收為一個數組，按照y的值排序，還需要按照層級排序，如果層級相同則按大小升序

理解：
其實就是層序遍歷+多了一個水平的定位（左子孫-1，右子孫+1）
因為元素的排序需要依照層級，所以層序遍歷為底，在棧中把單純存結點改成加入y定位的對象，可以清楚每個元素應該插入到哪個位置
中間配合哈希表收集同y的結點，排序後再插入res數組

代碼：

var verticalTraversal = function(root) {
    let zero = 0; // 紀錄y的位置，如果有-2，那麼0的位置就是在index = 2的位置（-2, -1, 0)
    const res = [];
    if (!root) {
        return [];
    }
    const stack = [{node: root, place: 0}]; // 把水平的y也放入棧中
    // 一般的層序遍歷
    while (stack.length) {
        const length = stack.length;
        const record = new Map();
        for (let i = 0; i < length; i++) {
            const {node, place} = stack.shift();
            if (node.left) {
            // 左子孫place - 1
                stack.push({node: node.left, place: place - 1});
            }
            if (node.right) {
                stack.push({node: node.right, place: place + 1});
            }
            // 使用哈希表紀錄是否有相同的y
            record.set(place, [...(record.get(place) || []), node.val]);
        }
        // 如果有多個相同層級的，先把值排序後再插入res數組
        record.forEach((value, key) => {travel(value.sort((a, b) => a - b), key)});
        // 將哈希表清除
        record.clear();
    }
    function travel(arr, place) {
        if (place < 0) {
        // 取絕對值，如果0在2的位置，表示最低只記錄到 -2 (-2, -1, 0)
        // 因為左右擴展都是一位一位的，不可能上層只有-2但是下面有-4
            const abs = Math.abs(place);
            if (abs <= zero) {
                res[zero - abs] = [...(res[zero - abs] || []), ...arr];
            } else {
                // abs > zero
                // 代表還沒記錄到 例如 3 > 2，要在數組頭加入 -3
                zero++;
                res.unshift(arr);
            }
        } else {
        // 正數，正常將值放入
            res[zero + place] = [...(res[zero + place] || []), ...arr];
        }
    }
    return res;
};