LeetCode二叉树的层次遍历Ⅱ（Python）——广度优先遍历

题目

解题思路

一开始看了题目，要求自底向上输出，第一反应是深度优先遍历，但仔细琢磨发现不对了，正如题中的例子，无论是前、中、后序遍历，都无法让15在9的前面被遍历到，没办法按题目想要的顺序输出（也可以强行用，后面说）。然后再看一眼题目，层次遍历？那就是要用广度优先遍历了。

广度优先遍历思路和104题二叉树最大深度的广度优先遍历很像，可以看这里。由于广度优先遍历没法直接自底向上式输出，所以最后要进行翻转，翻转这一步时间复杂度也为O(n)；del这一步，由于是删除最后一个元素，不需要搬动其他元素，所以时间复杂度为O(1)。总的时间复杂度还是O(n)。

执行结果为：

那如果非要用深度优先遍历呢？也不是没有办法，就是当遍历到一个结点时，res中已经建立好与这个结点深度对应的列表元素，那就只需要在相应位置填入数字就行。

实现方法有两种，一种是直接先遍历一遍，得到二叉树最大深度，直接建立res=[ [] * depth ]：

另一个方法就是当深度加1时，就在res的头部插入一个空的[]（此idea来自作者：powcai
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/solution/die-dai-he-di-gui-by-powcai-4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。）：

执行结果为：

但无论哪一种实际运行的时间空间上应该都不如广度优先遍历了。代码如下：