这题也是一点想法都没有,平常做的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而存在的。