二叉树的垂直遍历

题目描述

实现二叉树的垂直遍历，要求从左到右、从上到下遍历二叉树。

• 建立正确的坐标系统（垂直线和深度）
• 处理同一位置多个节点的排序规则
• 保持父节点关系的顺序继承

本题考查 树遍历算法、坐标计算 和 多维排序 的综合应用。

上述二叉树的垂直遍历结果为：[6,4,2,7,1,9,10,3,8,5]

核心知识点

坐标系统（代码中的实际定义）

代码使用 dfs(node, line, deep, parentLine)：

// 实际实现：
dfs(root.left,  line + 1, deep + 1, line)   // 左子树 line + 1
dfs(root.right, line - 1, deep + 1, line)   // 右子树 line - 1

也就是说：

• 根：line = 0, deep = 0
• 左子：列号 +1（而不是常规的 -1）
• 右子：列号 -1（而不是常规的 +1）

遍历完成后对列号执行：

Object.keys(tramap)
  .map(Number)
  .sort((a,b) => b - a) // 由大到小

由于列号被“左右反转”且再反向排序，最终效果仍是“视觉上从左到右”，只是实现路径绕了一圈。

深度 deep 递增方式与常规相同：根 0，子节点 +1。

排序规则（列层内排序）

每一列的节点按：

tramap[key].sort((a,b) => a.deep - b.deep || b.parentLine - a.parentLine)

优先级：

1. 深度升序（上到下）
2. parentLine 降序（父列号大的在前）

parentLine 来源于调用 dfs 时传入的父节点行号。因为列号采用了“左递增、右递减”策略，parentLine 降序意图是让“更靠左(视觉)的父节点派生的同层子节点”排在前面，但这种间接性可读性较差。

同一坐标出现多个节点的处理

当前实现没有显式记录 DFS 访问序号，只依赖：

• 深度 → 排前
• 相同深度 → parentLine 较大者在前（依赖列号与访问顺序的间接关系）

在极端结构（多分支产生相同 (line, deep) 且父列号相同）时，顺序不再严格受控（取决于插入数组的先后）。为获得稳定顺序，可额外记录 order（递增计数）并在比较器末尾增加 || a.order - b.order。

与“标准定义”差异对照

方面	标准常见写法	当前代码	影响
左子列号	col-1	line+1	语义反转，需配合最终列排序反向才能保持输出方向
右子列号	col+1	line-1	同上
列排序方向	升序（小→大）	降序（大→小）	与列号定义反向抵消效果
同列同深第三关键字	值 / 访问序号 / 无	parentLine(降序)	不直观，可能不稳定
稳定性	通常手动附加序号保证	未附加	边缘冲突时顺序不唯一

实现方案讨论

当前做法属于 “DFS 收集 + 事后排序” 模式：

• 时间复杂度：列集合排序 O(k log k) + 各列内部排序 Σ m_i log m_i；最坏 O(n log n)
• 空间复杂度：O(n) 存储每个节点结构 { value, deep, parentLine }

可替代策略：

• BFS + 哈希（列 → 队列），自然保证同深度层序，只有列内再按深度（已天然单调）减少比较器复杂度。
• DFS + Map<col, array> 并设置 minCol/maxCol，遍历范围 O(k) 避免 Object.keys 转换和排序（需改成顺序写入双端结构）。

差异与改进建议（按优先级）

1. 直接采用传统列号：左 -1，右 +1，列升序输出，删除“反向 + 再反排”的双重抵消逻辑。
2. 在节点结构中加入 order（全局自增），排序表达式改成：a.deep - b.deep || a.order - b.order 保证稳定性。
3. 用 Map 存列：Map<number, Array<NodeInfo>>，并实时维护 minCol / maxCol，输出时线性遍历范围避免排序。
4. 将 parentLine 逻辑替换为显式 DFS 顺序语义，提升可解释性。
5. 若数据量极大（>10^5 节点），考虑改写为迭代 DFS（显式栈）防止递归栈溢出。
6. 若需稳定重放，可加缓存：列遍历结果序列化成字符串做简单校验或比对。

参考：更直观的“标准版” DFS 实现草案

function verticalOrderStandard(root) {
  if (!root) return []
  const map = new Map() // col -> items
  let min = 0, max = 0, order = 0

  function dfs(node, col, row) {
    if (!node) return
    if (!map.has(col)) map.set(col, [])
    map.get(col).push({ val: node.value, row, order: order++ })
    min = Math.min(min, col)
    max = Math.max(max, col)
    dfs(node.left, col - 1, row + 1)
    dfs(node.right, col + 1, row + 1)
  }
  dfs(root, 0, 0)

  const res = []
  for (let c = min; c <= max; c++) {
    const list = map.get(c) || []
    list.sort((a,b) => a.row - b.row || a.order - b.order)
    for (const item of list) res.push(item.val)
  }
  return res
}

代码实现

// This is the class for the node
// you can use this directly as it is bundled with your code
export class Node {
  constructor(val) {
    this.value = val
    this.left = null
    this.right = null
  }
}
/**
 * @param {Node} root
 * @returns {number[]} result
 */
export default function traverse(root) {
  if (root === null) return []

  const tramap = {} // line -> Array<{ value, deep, parentLine }>
  const result = []

  function dfs(node, line, deep, parentLine) {
    if (!node) return
    if (!Object.hasOwn(tramap, line)) tramap[line] = []
    tramap[line].push({ value: node.value, deep, parentLine })
    // 注意：这里的方向与常规相反（左 +1 / 右 -1）
    dfs(node.left, line + 1, deep + 1, line)
    dfs(node.right, line - 1, deep + 1, line)
  }

  dfs(root, 0, 0, 0)

  Object.keys(tramap)
    .map(Number)
    .sort((a, b) => b - a) // 逆序以抵消列号反转
    .forEach((col) => {
      tramap[col]
        .sort((a, b) => a.deep - b.deep || b.parentLine - a.parentLine)
        .forEach(n => result.push(n.value))
    })
  return result
}

算法分析

方面	当前实现	说明
时间复杂度	O(n log n) 最坏	列集合排序 + 各列内部排序；若每列≈n 则近似 n log n
空间复杂度	O(n)	额外哈希表 + 递归栈（最坏深度 n）
稳定性	非严格	同列同行仅靠插入顺序 + parentLine（可能不唯一）
可读性	受坐标反转影响	逻辑需双重心智映射

优化潜力：改用正常列号 + 维护 min/max + 增加 order 字段即可在 O(n) 访问完后用 O(k + n log m_i)（接近 n log w，其中 w 为最大列宽）或用稳定插入避免列内排序（BFS）。

关键技术点

坐标维护

通过 (line, deep) 识别节点所在列与深度；采用“反向列号 + 逆序排序”实现视觉左→右。

数据结构

tramap: Record<number, Array<{ value, deep, parentLine }>>；适合快速追加，不适合稳定顺序判定。

排序器设计

a.deep - b.deep 保证自顶向下；b.parentLine - a.parentLine 借助父列号数值大小引导同层次次序，但耦合列号编码方式。

同位置冲突

未显式记录访问序号；可扩展：tramap[line].push({ ..., order: global++ }) 并在排序末尾追加 || a.order - b.order。

改进策略速览

问题	改进	预期收益
列号反向	使用传统列号	降低心智负担
稳定性不足	引入 order	明确冲突解决
shift/排序开销	Map + 范围遍历	减少列排序
递归栈溢出风险	迭代 DFS / BFS	支持大深度树
父列号语义不直观	替换 parentLine 排序为 order	可维护性提升

使用示例

// 构建测试二叉树
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
//  /         \
// 7           8

const root = new Node(1)
root.left = new Node(2)
root.right = new Node(3)
root.left.left = new Node(4)
root.left.right = new Node(5)
root.right.right = new Node(6)
root.left.left.left = new Node(7)
root.right.right.right = new Node(8)

// 垂直遍历
console.log(traverse(root))
// 输出: [7, 4, 2, 1, 5, 3, 6, 8]

// 分析遍历过程：
// 垂直线 -2: [7] (深度3)
// 垂直线 -1: [4] (深度2)
// 垂直线  0: [2, 1, 5] (深度1,0,2)
// 垂直线  1: [3] (深度1)
// 垂直线  2: [6] (深度2)
// 垂直线  3: [8] (深度3)

// 复杂示例：同位置多节点
//       1
//      / \
//     2   3
//    /|   |\
//   4 5   6 7
//    X     X
//   8 9   10 11

const complexRoot = new Node(1)
complexRoot.left = new Node(2)
complexRoot.right = new Node(3)
complexRoot.left.left = new Node(4)
complexRoot.left.right = new Node(5)
complexRoot.right.left = new Node(6)
complexRoot.right.right = new Node(7)
complexRoot.left.right.left = new Node(8)
complexRoot.left.right.right = new Node(9)
complexRoot.right.left.left = new Node(10)
complexRoot.right.left.right = new Node(11)

console.log(traverse(complexRoot))
// 需要特别注意8,9,10,11在垂直线0上的排序

// 边界情况测试
console.log(traverse(null)) // []
console.log(traverse(new Node(42))) // [42]

// 链式树测试
const chainRoot = new Node(1)
let current = chainRoot
for (let i = 2; i <= 5; i++) {
  current.left = new Node(i)
  current = current.left
}
console.log(traverse(chainRoot)) // [5, 4, 3, 2, 1]

// 性能测试
function buildPerfectTree(depth) {
  if (depth === 0)
    return null

  const root = new Node(depth)
  root.left = buildPerfectTree(depth - 1)
  root.right = buildPerfectTree(depth - 1)
  return root
}

const perfTree = buildPerfectTree(10)
console.time('traverse')
const result = traverse(perfTree)
console.timeEnd('traverse')
console.log(`Traversed ${result.length} nodes`)

// 验证结果正确性
function validateResult(root, result) {
  const allNodes = []

  function collectAll(node) {
    if (!node)
      return
    allNodes.push(node.value)
    collectAll(node.left)
    collectAll(node.right)
  }

  collectAll(root)

  // 检查节点数量
  if (allNodes.length !== result.length) {
    return false
  }

  // 检查所有节点都被包含
  const resultSet = new Set(result)
  return allNodes.every(val => resultSet.has(val))
}

console.log('Result valid:', validateResult(root, traverse(root)))

扩展思考

1. 支持自定义排序规则

function customTraverse(root, compareFn) {
  const nodes = []

  function dfs(node, col, row, parent) {
    if (!node)
      return

    nodes.push({
      value: node.value,
      col,
      row,
      parent,
      node,
    })

    dfs(node.left, col - 1, row + 1, node)
    dfs(node.right, col + 1, row + 1, node)
  }

  dfs(root, 0, 0, null)

  // 使用自定义比较函数
  nodes.sort(compareFn)

  return nodes.map(n => n.value)
}

// 使用示例：按值排序
function byValue(a, b) {
  if (a.col !== b.col)
    return a.col - b.col
  if (a.row !== b.row)
    return a.row - b.row
  return a.value - b.value // 同位置按值排序
}

2. 支持水平遍历

function horizontalTraverse(root) {
  if (!root)
    return []

  const rowMap = new Map()

  function dfs(node, col, row) {
    if (!node)
      return

    if (!rowMap.has(row)) {
      rowMap.set(row, [])
    }

    rowMap.get(row).push([node.value, col])

    dfs(node.left, col - 1, row + 1)
    dfs(node.right, col + 1, row + 1)
  }

  dfs(root, 0, 0)

  const result = []
  const sortedRows = Array.from(rowMap.keys()).sort((a, b) => a - b)

  for (const row of sortedRows) {
    const nodes = rowMap.get(row)
    nodes.sort((a, b) => a[1] - b[1]) // 按列排序
    result.push(...nodes.map(([val]) => val))
  }

  return result
}

3. 支持对角线遍历

function diagonalTraverse(root) {
  if (!root)
    return []

  const diagonalMap = new Map()

  function dfs(node, col, row) {
    if (!node)
      return

    // 对角线索引 = col + row
    const diagonal = col + row

    if (!diagonalMap.has(diagonal)) {
      diagonalMap.set(diagonal, [])
    }

    diagonalMap.get(diagonal).push({
      value: node.value,
      col,
      row,
    })

    dfs(node.left, col - 1, row + 1)
    dfs(node.right, col + 1, row + 1)
  }

  dfs(root, 0, 0)

  const result = []
  const sortedDiagonals = Array.from(diagonalMap.keys()).sort((a, b) => a - b)

  for (const diag of sortedDiagonals) {
    const nodes = diagonalMap.get(diag)
    // 同对角线按列排序
    nodes.sort((a, b) => a.col - b.col)
    result.push(...nodes.map(n => n.value))
  }

  return result
}

4. 支持层次统计

function traverseWithStats(root) {
  if (!root)
    return { result: [], stats: {} }

  const nodes = []
  const stats = {
    totalNodes: 0,
    maxDepth: 0,
    columnRange: [0, 0],
    nodesPerColumn: new Map(),
    nodesPerRow: new Map(),
  }

  function dfs(node, col, row) {
    if (!node)
      return

    stats.totalNodes++
    stats.maxDepth = Math.max(stats.maxDepth, row)
    stats.columnRange[0] = Math.min(stats.columnRange[0], col)
    stats.columnRange[1] = Math.max(stats.columnRange[1], col)

    // 统计每列节点数
    stats.nodesPerColumn.set(col, (stats.nodesPerColumn.get(col) || 0) + 1)
    stats.nodesPerRow.set(row, (stats.nodesPerRow.get(row) || 0) + 1)

    nodes.push([node.value, col, row])

    dfs(node.left, col - 1, row + 1)
    dfs(node.right, col + 1, row + 1)
  }

  dfs(root, 0, 0)

  nodes.sort((a, b) => {
    if (a[1] !== b[1])
      return a[1] - b[1]
    return a[2] - b[2]
  })

  return {
    result: nodes.map(([val]) => val),
    stats,
  }
}

5. 支持可视化输出

function visualizeTraversal(root) {
  if (!root)
    return ''

  const grid = new Map()
  let minCol = 0
  let maxCol = 0
  let maxRow = 0

  function dfs(node, col, row) {
    if (!node)
      return

    minCol = Math.min(minCol, col)
    maxCol = Math.max(maxCol, col)
    maxRow = Math.max(maxRow, row)

    if (!grid.has(row)) {
      grid.set(row, new Map())
    }
    grid.get(row).set(col, node.value)

    dfs(node.left, col - 1, row + 1)
    dfs(node.right, col + 1, row + 1)
  }

  dfs(root, 0, 0)

  // 构建可视化字符串
  let result = ''
  for (let row = 0; row <= maxRow; row++) {
    let line = ''
    for (let col = minCol; col <= maxCol; col++) {
      if (grid.has(row) && grid.get(row).has(col)) {
        line += grid.get(row).get(col).toString().padStart(3)
      }
      else {
        line += '   '
      }
    }
    result += `${line.trim()}\n`
  }

  return result
}

// 使用示例
console.log(visualizeTraversal(root))
//   2
// 4   1   3
// 7     5     6
//               8