# 【基础篇 - Day 18】 2020-11-18 - 987. 二叉树的垂序遍历（03. 树 ）
# 题目描述
# 入选理由
1.二叉树的奇葩遍历很多，这算一种。 2.和前面学的知识有联动
# 题目描述
给定二叉树，按垂序遍历返回其结点值。 对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。 把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。 如果两个结点位置相同，则首先报告的结点值较小。 按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。 示例 1： 输入：[3,9,20,null,null,15,7] 输出：[[9],[3,15],[20],[7]] 解释： 在不丧失其普遍性的情况下，我们可以假设根结点位于 (0, 0)： 然后，值为 9 的结点出现在 (-1, -1)； 值为 3 和 15 的两个结点分别出现在 (0, 0) 和 (0, -2)； 值为 20 的结点出现在 (1, -1)； 值为 7 的结点出现在 (2, -2)。 示例 2： 输入：[1,2,3,4,5,6,7] 输出：[[4],[2],[1,5,6],[3],[7]] 解释： 根据给定的方案，值为 5 和 6 的两个结点出现在同一位置。 然而，在报告 "[1,5,6]" 中，结点值 5 排在前面，因为 5 小于 6。 提示： 树的结点数介于 1 和 1000 之间。 每个结点值介于 0 和 1000 之间。https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(nlogn) 应该就是 sort 的时间复杂度 + n
空间复杂度: O(n)
bfs 对每个节点进行求坐标
然后对坐标进行排序，
- 优先 X 轴
- 然后 Y 轴
- 然后进行值的比较
这个排序卡了我好久尬住了，
var verticalTraversal = function (root) {
let queue = [root]
let map = {}
map[root.val] = [0, 0, root.val]
while (queue.length) {
let curr = queue.shift()
const val = map[curr.val]
if (curr.left) {
queue.push(curr.left)
map[curr.left.val] = [val[0] - 1, val[1] - 1, curr.left.val]
}
if (curr.right) {
queue.push(curr.right)
map[curr.right.val] = [val[0] + 1, val[1] - 1, curr.right.val]
}
}
const newArr = Object.values(map).sort((a, b) => {
if (a[0] - b[0] !== 0) return a[0] - b[0]
if (b[1] - a[1] === 0) return a[2] - b[2]
return b[1] - a[1]
})
const res = []
let mark = -1
for (let i = 0; i < newArr.length; i++) {
if (!newArr[i - 1] || newArr[i][0] !== newArr[i - 1][0]) {
mark++
}
if (!res[mark]) res.push([])
res[mark].push(newArr[i][2])
}
return res
};
# 解法二
时间复杂度：O(nlogn)
空间复杂度: O(n)
dfs 模板换一下就好了
var verticalTraversal = function (root) {
let map = {}
function dfs(root, x, y) {
if (!root) return
map[root.val] = [x, y, root.val]
dfs(root.left, x - 1, y - 1)
dfs(root.right, x + 1, y - 1)
return root
}
dfs(root, 0, 0)
const newArr = Object.values(map).sort((a, b) => {
if (a[0] - b[0] !== 0) return a[0] - b[0]
if (b[1] - a[1] === 0) return a[2] - b[2]
return b[1] - a[1]
})
const res = []
let mark = -1
for (let i = 0; i < newArr.length; i++) {
if (!newArr[i - 1] || newArr[i][0] !== newArr[i - 1][0]) {
mark++
}
if (!res[mark]) res.push([])
res[mark].push(newArr[i][2])
}
return res
};
https://github.com/leetcode-pp/91alg-2/issues/44#issuecomment-729346754