987. Vertical Order Traversal of a Binary Tree

[Tcdian]

987. Vertical Order Traversal of a Binary Tree

给定二叉树，按垂序遍历返回其结点值。

对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。

把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。

如果两个结点位置相同，则首先报告的结点值较小。

按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。

Example 1

Input: [3,9,20,null,null,15,7]
Output: [[9],[3,15],[20],[7]]
Explanation: 
Without loss of generality, we can assume the root node is at position (0, 0):
Then, the node with value 9 occurs at position (-1, -1);
The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);
The node with value 20 occurs at position (1, -1);
The node with value 7 occurs at position (2, -2).

Example 2

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

Note

• 树的结点数介于 1 和 1000 之间。
• 每个结点值介于 0 和 1000 之间。

[Tcdian]

Solution

• JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var verticalTraversal = function(root) {
    if (root === null) {
        return [];
    }
    const cache = new Map();
    const queue = [[root, 0, 0]];
    while (queue.length !== 0) {
        const [node, offset, level] = queue.shift();
        let cloumn = [...cache.get(offset) || []];
        let position = cloumn.length;
        while(
            position > 0
            && cloumn[position - 1][1] === level
            && cloumn[position - 1][0] > node.val
        ) {
            position -= 1;
        }
        cloumn.splice(position, 0, [node.val, level]);
        cache.set(offset, cloumn);
        if (node.left) {
            queue.push([node.left, offset - 1, level + 1]);
        }
        if (node.right) {
            queue.push([node.right, offset + 1, level + 1]);
        }
    }
    return [...cache.entries()].sort(([a], [b]) => a - b).map(([,cloumn]) => cloumn.map(([val]) => val));
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function verticalTraversal(root: TreeNode | null): number[][] {
    if (root === null) {
        return [];
    }
    const cache: Map<number, [number, number][]> = new Map();
    const queue: [TreeNode, number, number][] = [[root, 0, 0]];
    while (queue.length !== 0) {
        const [node, offset, level] = queue.shift() as [TreeNode, number, number];
        let cloumn = [...cache.get(offset) || []];
        let position = cloumn.length;
        while(
            position > 0
            && cloumn[position - 1][1] === level
            && cloumn[position - 1][0] > node.val
        ) {
            position -= 1;
        }
        cloumn.splice(position, 0, [node.val, level]);
        cache.set(offset, cloumn);
        if (node.left) {
            queue.push([node.left, offset - 1, level + 1]);
        }
        if (node.right) {
            queue.push([node.right, offset + 1, level + 1]);
        }
    }
    return [...cache.entries()].sort(([a], [b]) => a - b).map(([,cloumn]) => cloumn.map(([val]) => val));
};