987. 二叉树的垂序遍历

二叉树的垂序遍历

• 难度: hard
• 原始链接: https://leetcode.cn/problems/vertical-order-traversal-of-a-binary-tree
• 标签: 排序

解法一: 排序

go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func verticalTraversal(root *TreeNode) [][]int {
  var lists [][]int
  var dfs func(*TreeNode, int, int)
  dfs = func(node *TreeNode, col, row int) {
    if node == nil {
      return
    }
    lists = append(lists, []int{col, row, node.Val})
    dfs(node.Left, col-1, row+1)
    dfs(node.Right, col+1, row+1)
  }
  dfs(root, 0, 0)
  sort.Slice(lists, func(i, j int) bool {
    if lists[i][0] != lists[j][0] {
      return lists[i][0] <= lists[j][0]
    }
    if lists[i][1] != lists[j][1] {
      return lists[i][1] <= lists[j][1]
    }
    return lists[i][2] <= lists[j][2]
  })
  preCol := -1001
  var ans [][]int
  for _, list := range lists {
    if preCol == list[0] {
      last := len(ans) - 1
      ans[last] = append(ans[last], list[2])
    } else {
      preCol = list[0]
      ans = append(ans, []int{list[2]})
    }
  }
  return ans
}