题目

题目来源：力扣（LeetCode）

给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

对位于 (row, col) 的每个结点而言，其左右子结点分别位于 (row + 1, col - 1) 和 (row + 1, col + 1) 。树的根结点位于 (0, 0) 。

二叉树的 垂序遍历 从最左边的列开始直到最右边的列结束，按列索引每一列上的所有结点，形成一个按出现位置从上到下排序的有序列表。如果同行同列上有多个结点，则按结点的值从小到大进行排序。

返回二叉树的 垂序遍历 序列。

示例 1：
image.png

输入：root = [3,9,20,null,null,15,7]
输出：[[9],[3,15],[20],[7]]
解释：
列 -1 ：只有结点 9 在此列中。
列 0 ：只有结点 3 和 15 在此列中，按从上到下顺序。
列 1 ：只有结点 20 在此列中。
列 2 ：只有结点 7 在此列中。

示例 2：
image.png

输入：root = [1,2,3,4,5,6,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
列 -2 ：只有结点 4 在此列中。
列 -1 ：只有结点 2 在此列中。
列 0 ：结点 1 、5 和 6 都在此列中。
1 在上面，所以它出现在前面。
5 和 6 位置都是 (2, 0) ，所以按值从小到大排序，5 在 6 的前面。
列 1 ：只有结点 3 在此列中。
列 2 ：只有结点 7 在此列中。

示例 3：
image.png

输入：root = [1,2,3,4,6,5,7]
输出：[[4],[2],[1,5,6],[3],[7]]
解释：
这个示例实际上与示例 2 完全相同，只是结点 5 和 6 在树中的位置发生了交换。
因为 5 和 6 的位置仍然相同，所以答案保持不变，仍然按值从小到大排序。

思路分析

我们可以从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号row，列号 col 以及值 value。在遍历完成后，我们按照 col 为第一关键字升序，row 为第二关键字升序，value 为第三关键字升序，对所有的节点进行排序即可。

在排序完成后，我们还需要按照题目要求，将同一列的所有节点放入同一个数组中。因此，我们可以对 nodes 进行一次遍历，并在遍历的过程中记录上一个节点的列号 lastcol。如果当前遍历到的节点的列号 col 与 lastcol 相等，则将该节点放入与上一个节点相同的数组中，否则放入不同的数组中。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[][]}
  12.  */
  13. var verticalTraversal = function (root) {
  14.   const nodes = [];
  15.   // 1.从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号ow，列号 col 以及值 value。
  16.   dfs(root, 0, 0, nodes);
  17.   // 2.遍历完成后，对所有的节点进行排序。
  18.   // 按照 col 为第一关键字升序，row 为第二关键字升序，value 为第三关键字升序，对所有的节点进行排
  19.   nodes.sort((a, b) => {
  20.     if (a[0] !== b[0]) {
  21.       // 首先按照 列 升序排序
  22.       return a[0] - b[0];
  23.     } else if (a[1] !== b[1]) {
  24.       // 然后按照 行 升序排序
  25.       return a[1] - b[1];
  26.     } else {
  27.       // 最后按照 值 升序排序
  28.       return a[2] - b[2];
  29.     }
  30.   });
  31.   // 3.对 nodes 进行一次遍历,将行号 row相等的value值放到同一个数组中。
  32.   const ret = [];
  33.   // 在遍历过程中记录 上一个节点的列号
  34.   let lastCol = -Number.MAX_VALUE;
  35.   // 遍历 nodes，如果当前遍历到的节点的列号 col 与 lastCol 相等，
  36.   // 则将该节点放入与上一个节点相同的数组中，否则放入不同的数组中
  37.   for (const x of nodes) {
  38.     // 当前遍历到的节点的列号 与 上一个节点的列号 不相同，需要将其放入新的数组中，因此在 ret 加入一个空数组
  39.     if (lastCol !== x[0]) {
  40.       lastCol = x[0];
  41.       ret.push([]);
  42.     }
  43.     // 将节点值放入相同列数组中
  44.     ret[ret.length - 1].push(x[2]);
  45.   }
  46.   return ret;
  47. };
  48. // <!-- 创建树遍历函数 -->
  49. var dfs = function (node, row, col, nodes) {
  50.   if (node === null) {
  51.     return;
  52.   }
  53. // 记录当前节点的行号ow，列号 col 以及值 value
  54.   nodes.push([col, row, node.val]);
  55.   // 遍历左子树
  56.   dfs(node.left, row + 1, col - 1, nodes);
  57.   // 遍历右子树
  58.   dfs(node.right, row + 1, col + 1, nodes);
  59. }