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)，需要记录每个节点的坐标和值。