这种题目 和 索引数组一样麻烦，很容易被绕晕了。

987. 二叉树的垂序遍历

这样的 map
image.png
代码实现

  1. var verticalTraversal = function(root) {
  2.     let map = new Map();
  3.     let res = [];
  4.     const dfs = (node, row, col) => {
  5.         if(node == null) return 0;
  6.          map.set(col, [{
  7.             val: node.val,
  8.             row: row
  9.         }, ...(map.get(col) || [])] )
  10.         dfs(node.left, row + 1, col - 1);
  11.         dfs(node.right, row + 1, col + 1);
  12.     }
  14.     dfs(root, 0, 0);
  15.     for(let [key, values] of map.entries() ) {
  16.         values.sort((a, b) => {
  17.             if(a.row == b.row) {
  18.                 return a.val - b.val
  19.             }
  20.             return a.row - b.row;
  21.         })
  22.         if(key >= 0) {
  23.             res.push(values.map(item => item.val))
  24.         } else {
  25.             res.unshift(values.map(item => item.val))
  26.         }
  28.     }
  29.     return res;
  30. };

1) 要按照， map key 来排序：
image.png
而本题的插入正好是有序的，因此不需要排序 key
2）先按 row 排序，如果 row 相等，则按 value 排序。代码里正好倒着写。

  1. 比较模型：

[row, col, val]

垂序遍历：

  1. col
  2. row

  3. val

    1. res.sort((a, b) => {
    2. if (a[1] !== b[1]) {
    3.  return a[1] - b[1];
    4. } else if (a[0] !== b[0]) {
    5.  return a[0] - b[0];
    6. } else {
    7.  return a[2] - b[2];
    8. } 
    9. });

    合并同列项：这个技法很牛逼，如何在遍历的过程中合并key相同的元素

    1. const ans = [];
    2. let lastcol = -Number.MAX_VALUE;
    3. for (const tuple of nodes) {
    4.    let [row, col, value] = tuple;
    5.    if (col !== lastcol) {
    6.        lastcol = col;
    7.        ans.push([]);
    8.    }
    9.    ans[ans.length - 1].push(value);
    10. }
    11. return ans;

    完整代码： ```javascript var verticalTraversal = function(root) { const nodes = []; dfs(root, 0, 0, nodes); nodes.sort((tuple1, tuple2) => {

    1.  if (tuple1[0] !== tuple2[0]) {
    2.      return tuple1[0] - tuple2[0];
    3.  } else if (tuple1[1] !== tuple2[1]) {
    4.      return tuple1[1] - tuple2[1];
    5.  } else {
    6.      return tuple1[2] - tuple2[2];
    7.  }

    });

    const ans = []; let lastcol = -Number.MAX_VALUE; for (const tuple of nodes) { let [row, col, value] = tuple;

    1.  if (col !== lastcol) {
    2.      lastcol = col;
    3.      ans.push([]);
    4.  }
    5.  ans[ans.length - 1].push(value);

    } return ans; }

const dfs = (node, row, col, nodes) => { if (node === null) { return; } nodes.push([col, row, node.val]); dfs(node.left, row + 1, col - 1, nodes); dfs(node.right, row + 1, col + 1, nodes); }

  1. 2.双层map 递归 sort 
  2. ```javascript
  3. var verticalTraversal = function(root) {
  4.     let map = new Map()
  6.     function dfs(root, row, col) {
  7.         if (!root) return
  8.         if (!map.has(col)) {
  9.             map.set(col, new Map())
  10.         }
  11.         const item = map.get(col)
  12.         if (!item.has(row)) {
  13.             item.set(row, [])
  14.         }
  15.         item.get(row).push(root.val)
  16.         dfs(root.left, row + 1, col - 1)
  17.         dfs(root.right, row + 1, col + 1)
  18.     }
  19.     dfs(root, 0, 0)
  21.     let arr = []
  22.     for (let col of map) {
  23.         arr.push(col)
  24.     }
  26.     return arr.sort((a, b) => a[0] - b[0]).map(item => {
  27.         const arr = []
  28.         for (let row of item[1]) {
  29.             arr.push(row)
  30.         }
  31.         arr.sort((a, b) => a[0] - b[0])
  32.         return arr.map(it => {
  33.             if (it[1].length > 1) { // 这里排序的特殊之处
  34.                 it[1].sort((a, b) => a - b)
  35.             }
  36.             return it[1]
  37.         }).flat()
  38.     })
  39. };

314. 二叉树的垂直遍历

和 987 相同题目，还更简单