# 21-05-27-二叉树的垂序遍历
# 题目地址
https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree/
# 题目描述
给定二叉树，按垂序遍历返回其结点值。
对位于 (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 之间。
# 前置知识
二叉树遍历方式与排序
# 思路
- 前序遍历记录坐标值和节点值。
- 根据坐标值和节点值排序：优先级：列坐标 > 行坐标 > 节点值。
- 组装结果数据，将列坐标相同的放到同一个数组中，不同列坐标放不同数组，返回一个二维数组。
# 代码
/**
* 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[][]}
*/
var verticalTraversal = function (root) {
if (!root) return [];
const locationList = [];
// 前序遍历记录坐标点
dfs(root, 0, 0);
// 排序
locationList.sort((a, b) => {
// 先根据列坐标排
if (a[1] !== b[1]) return a[1] - b[1];
// 再根据行坐标排
if (a[0] !== b[0]) return a[0] - b[0];
// 再根据值大小排
return a[2] - b[2];
});
const length = locationList.length;
const result = [[locationList[0][2]]];
let prev = locationList[0][1];
// 组装结果数据 循环 遇到列坐标不同就新push一个数组 相同就push到上一个数组的尾部
for (let i = 1; i < length; i++) {
if (locationList[i][1] !== prev) {
result.push([locationList[i][2]]);
prev = locationList[i][1];
} else {
result[result.length - 1].push(locationList[i][2]);
}
}
return result;
function dfs(root, x, y) {
if (root) {
locationList.push([x, y, root.val]);
dfs(root.left, x + 1, y - 1);
dfs(root.right, x + 1, y + 1);
}
}
};
# 复杂度分析
- 时间复杂度：排序O(NlogN)
- 空间复杂度：O(N)