Vertical Traversal Tree

这题也是一点想法都没有,平常做的traversal再怎么样也是一个Horizontal的, vertical的话,怎么知道谁和你是一列的。。。

答案搬运工。。【看完答案我真心觉得这题是Hard level】

答案采用了BFS的方式,最厉害的地方就是他做了一个cols的queue。然后结合了一下HasMap. 同一个col的, which will have same hashkey, 都会放在同一个list里。当到了Leaf的时候,把所有同一个col里的赛进res list里。

还有一个特别tricky的地方就是。 我们一开始给Root 一个col value 为0的值。 但是我们不知道left subtree到底能够延伸的多left, right subtree能延伸的多right。有可能最左边col=-100000... 最右边col = 1000000. 我们都不知道,所有我们用了一个min, max 来记录最左和最右的col值。当col刷新了原本最远的col时候,我们要update一下min, max.

然后还有一个queue  q,就是为了按照BFS的顺序visit Node而存在的。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容