987.二叉树的垂序遍历

链接：987.二叉树的垂序遍历
难度：Hard
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树、排序
简介：给你二叉树的根结点 root ，请你设计算法计算二叉树的 垂序遍历 序列。

题解 1 - typescript

• 编辑时间：2021-07-31
• 执行用时：92ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：哈希储存。

function verticalTraversal(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const map = new Map<number, number[][]>();
  order(root, 0, 0);
  const list = [...map.entries()]
    .sort(([col1], [col2]) => col1 - col2)
    .map(([, list]) =>
      list
        .sort(([, row1, val1], [, row2, val2]) => (row1 === row2 ? val1 - val2 : row1 - row2))
        .map(([, , v]) => v)
    );
  return list;
  function order(node: TreeNode | null, row: number, col: number) {
    if (node === null) return null;
    let list = map.get(col);
    if (!list) map.set(col, (list = []));
    list.push([col, row, node.val]);
    order(node.left, row + 1, col - 1);
    order(node.right, row + 1, col + 1);
  }
}

题解 2 - typescript

• 编辑时间：2021-10-25
• 执行用时：88ms
• 内存消耗：39.7MB
• 编程语言：typescript
• 解法介绍：哈希存储。

function verticalTraversal(root: TreeNode | null): number[][] {
  if (root === null) return [];
  const map = new Map<number, [number, number][]>();
  dfs(root);
  return Array.from(map.entries())
    .sort(([a], [b]) => a - b)
    .map(([, arr]) =>
      arr
        .sort(([num1, row1], [num2, row2]) => (row1 === row2 ? num1 - num2 : row1 - row2))
        .map(([num]) => num)
    );
  function dfs(node: TreeNode | null, row = 0, col = 0) {
    if (node === null) return;
    let arr = map.get(col);
    if (!arr) map.set(col, (arr = []));
    arr.push([node.val, row]);
    dfs(node.left, row + 1, col - 1);
    dfs(node.right, row + 1, col + 1);
  }
}

题解 3 - python

• 编辑时间：2024-02-13
• 执行用时：49ms
• 内存消耗：16.71MB
• 编程语言：python
• 解法介绍：dfs。

class Solution:
    def verticalTraversal(self, root: Optional[TreeNode]) -> List[List[int]]:
        map = defaultdict(defaultdict)
        def dfs(node: Optional[TreeNode], row: int, col: int):
            if not node: return
            if row not in map[col]: map[col][row] = []
            map[col][row].append(node.val)
            if node.left: dfs(node.left, row + 1, col - 1)
            if node.right: dfs(node.right, row + 1, col + 1)
        dfs(root, 0, 0)
        arr = []
        for _, cols in sorted(map.items()):
            item = []
            for _, values in sorted(cols.items()):
                item += sorted(values)
            arr.append(item)
        return arr