Binary Tree Vertical Order Traversal

Description

null

Solution(javascript)

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
const verticalOrder = function (root) {
  const map = {}
  if (!root) {
    return []
  }
  let current = [root]
  root.order = 0
  while (current.length > 0) {
    const next = []
    current.forEach((node) => {
      map[node.order] = map[node.order] || []
      map[node.order].push(node.val)
      if (node.left) {
        node.left.order = node.order - 1
        next.push(node.left)
      }
      if (node.right) {
        node.right.order = node.order + 1
        next.push(node.right)
      }
    })
    current = next
  }
  return Object.keys(map).sort((a, b) => Number(a) - Number(b)).map(key => map[key])
}