leetcode 987题 二叉树的垂序遍历
给定二叉树，按垂序遍历返回其结点值。
对位于 (X, Y) 的每个结点而言，其左右子结点分别位于 (X-1, Y-1) 和 (X+1, Y-1)。
把一条垂线从 X = -infinity 移动到 X = +infinity ，每当该垂线与结点接触时，我们按从上到下的顺序报告结点的值（ Y 坐标递减）。
如果两个结点位置相同，则首先报告的结点值较小。
按 X 坐标顺序返回非空报告的列表。每个报告都有一个结点值列表。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例 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)。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/vertical-order-traversal-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
1 利用 bfs ，遍历所有的节点，把所有的节点记录在一个对象中，这个对象保存了所在节点的val，坐标x，坐标y信息
2 对于对象的 key 进行排序，得到 key 排序数组
3 key 排序数组依次遍历，得到最终的结果
注意：
需要遵守以下规则：
- 坐标 x 值越小，排在前面
- x 值相等，y 值越大，排在前面
- x 值， y 值都相等，比较两者的 val，val 值小的排在前面
代码
function verticalTraversal(root) {
if (root === null) return null;
// bfs
const arr = [{node: root, x: 0, y: 0}];
const obj = {};
while (arr.length) {
const curr = arr.shift();
const {node, x, y} = curr;
const {left, right} = node;
if (obj[x] === undefined) {
obj[x] = [{val: node.val, y}];
} else {
obj[x].push({val: node.val, y});
}
if (left) {
arr.push({node: left, x: x - 1, y: y - 1});
}
if (right) {
arr.push({node: right, x: x + 1, y: y - 1});
}
}
// sort
const keysArr = Object.keys(obj).sort((a, b) => a - b);
// compose res
const res = [];
keysArr.forEach(key => {
// sort
obj[key].sort((a, b) => {
// 当两者y相等，val值小的排在前面
if (a.y === b.y) {
return a.val - b.val;
}
// y值大的排在前面
return b.y - a.y;
});
// 拼凑结果
const tempArr = [];
obj[key].forEach(item => {
tempArr.push(item.val);
});
res.push(tempArr);
});
return res;
}
复杂度分析
- 时间复杂度: O(n)
- 空间复杂度: O(n)