BFE.devAI解答 - JavaScript 代码题
137. 垂直遍历二叉树

解题思路：

1. 遍历二叉树，记录每个节点的坐标，以根节点为原点，左侧节点 x 坐标减 1，右侧节点 x 坐标加 1，深度 y 坐标加 1；
2. 将记录的节点按照 x 坐标从小到大排序，相同 x 坐标的按照 y 坐标从小到大排序；
3. 将排序后的节点的值按照顺序存入数组中即为垂直遍历的结果。

具体实现：

function verticalTraversal(root) {
  const nodeArr = []; // 记录每个节点的坐标和值

  function traverse(node, x = 0, y = 0) {
    if (!node) {
      return;
    }
    nodeArr.push({val: node.val, x, y});
    traverse(node.left, x - 1, y + 1);
    traverse(node.right, x + 1, y + 1);
  }

  traverse(root);
  nodeArr.sort((a, b) => {
    if (a.x !== b.x) {
        return a.x - b.x;
    } else if (a.y !== b.y) {
        return a.y - b.y;
    } else {
        return a.val - b.val;
    }
  });

  return nodeArr.map(item => item.val);
}

时间复杂度：O(nlogn)，其中 n 为树的节点个数，需要遍历每个节点并排序。

空间复杂度：O(n)，需要记录每个节点的坐标和值。