【Day 45 】2021-06-23 - Top-View-of-a-Tree
题目描述
op-View-of-a-Tree
入选理由
暂无
题目地址
https://binarysearch.com/problems/Top-View-of-a-Tree
前置知识
- BFS
- 哈希表
题目描述
Given a binary tree root, return the top view of the tree, sorted left-to-right.
Constraints
n ≤ 100,000 where n is the number of nodes in root
我的回答
解法一
时空复杂度
时间复杂度：O(n)
空间复杂度: O(nÏ)
class Solution {
solve(root) {
let result = []
let map = new Map()
let queen = [[root, 0]]
while (queen.length) {
let [curr, x] = queen.shift()
if (!map.has(x)) {
map.set(x, curr.val)
}
if (curr.left) {
queen.push([curr.left, x - 1])
}
if (curr.right) {
queen.push([curr.right, x + 1])
}
}
return Array.from(map).sort((a, b) => a[0] - b[0]).map(v => v[1])
}
}