987. 二叉树的垂序遍历

[zpc7]

987. 二叉树的垂序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
function verticalTraversal(root) {
  let arr = [];

  // 计算坐标
  // (row,col) --> 行,列 --> 树的高度(当前在第几层), 左右子树(左边还是右边)
  const dfs = (root, row, col) => {
    if (!root) return;

    arr.push({ x: row, y: col, val: root.val })

    dfs(root.left, row + 1, col - 1);
    dfs(root.right, row + 1, col + 1);
  }
  dfs(root, 0, 0)

//  console.log('arr:', arr)

  // 按照 Y 分组(groupBy)
  let map = {};
  for (let item of arr) {
    if (map[item.y]) {
      map[item.y].push({ x: item.x, val: item.val })
    } else {
      map[item.y] = [{ x: item.x, val: item.val }];
    }
  }
  
  // console.log("map:", map);

  // 按照 Map的key 升序+值的升序排列(注意是优先按照从上到下,如果坐标一样再升序)
  return Object.keys(map).sort((a, b) => Number(a) - Number(b)).map(key => map[key].sort((a, b) => {
    const isRowSame = a.x - b.x;
    return isRowSame === 0 ? a.val - b.val : isRowSame;
  }).map(i => i.val))
};

按照如下示例数据为例:

const data = {
  val: 100,
  left: {
    val: 2,
    left: {
      val: 4
    },
    right: {
      val: 18
    }
  },
  right: {
    val: 3,
    left: {
      val: 5
    },
    right: {
      val: 7
    }
  }
}

console.log 每一步打印出的结果是:

arr: [
  { x: 0, y: 0, val: 100 },
  { x: 1, y: -1, val: 2 },
  { x: 2, y: -2, val: 4 },
  { x: 2, y: 0, val: 18 },
  { x: 1, y: 1, val: 3 },
  { x: 2, y: 0, val: 5 },
  { x: 2, y: 2, val: 7 }
]
map: {
  '0': [ { x: 0, val: 100 }, { x: 2, val: 18 }, { x: 2, val: 5 } ],
  '1': [ { x: 1, val: 3 } ],
  '2': [ { x: 2, val: 7 } ],
  '-1': [ { x: 1, val: 2 } ],
  '-2': [ { x: 2, val: 4 } ]
}
[ [ 4 ], [ 2 ], [ 100, 5, 18 ], [ 3 ], [ 7 ] ]