关于binary tree level order traversal的变形题

我最近在复习这道题，以及它的变形题比如zigzag traversal和bottom－up traversal，但是发现之前自己的解法都是先按照正常的traversal去做，只不过在最后return 结果之前把array list里的数组reverse一下。想问一下大家这么做是不是违反了面试官的本意，会不会被吐槽。还是说只要能把最终结果得出来，这种小trick也无妨？谢谢大家

bottom-up traversal如果用BFS来做的话，必须先正序遍历然后倒过来，这个无可厚非；但对于zigzag traversal，如果面试官follow up说“假设我们的树很大且非常不平衡，现在不要求你返回一个array list，而是要打印出每一层即可”的话，这种情况下，先保存所有的结果的做法就会耗掉很多内存。

总之，只要能100%返回正确结果，且满足面试官提出的时空复杂度，这题就应该算能通过；但是，面试官可能会另外提出一些优化要求，如果这个follow up答不上来的话，就不太好看了。所以最好能够掌握此题的优化解法。

楼上大神请问zigzag traversal有没有什么办法可以不存当前结果？我的意思不存当前level的结果，直接得到reverse的结果。我看了LC所有最优解，都要开一个size为当前level个数的大List，再把数放到相应位置，没法直接就能从后往前的。

我换一种问法吧，比如每一个level的size都很大，你不知道这个level会有多大，怎样才能reverse

seonghae 发表于 2015-11-15 00:51
楼上大神请问zigzag traversal有没有什么办法可以不存当前结果？我的意思不存当前level的结果，直接得到rev ...

是说的一层用queue.一层用stack的解法么？

seonghae 发表于 2015-11-15 13:51
楼上大神请问zigzag traversal有没有什么办法可以不存当前结果？我的意思不存当前level的结果，直接得到rev ...

抱歉我没说清楚。用BFS的话保存一层的所有元素是不可避免的，所以如果每一层元素都很多的话（比如树是complete的），那必然很耗内存。我理解的楼主的意思是说，先把所有层的traversal都存起来，然后reverse偶数层。我2楼帖子仅是针对这个理解做出的评论。

stellari 发表于 2015-11-16 08:15
抱歉我没说清楚。用BFS的话保存一层的所有元素是不可避免的，所以如果每一层元素都很多的话（比如树是com ...

嗯嗯同意！每一层是一定要存的～

stellari 发表于 2015-11-15 16:15
抱歉我没说清楚。用BFS的话保存一层的所有元素是不可避免的，所以如果每一层元素都很多的话（比如树是com ...

嗯嗯这就是我的意思，感谢大神的回复还有这个follow up的问法～