第一遍的时候写错了，直接写成先根序遍历了可还行。这题就是很典型的层序遍历而已，用一个队列记录每一层的节点，在遍历每层的时候将答案加到res里。我把jz055I.二叉树的深度这个题的代码拿来稍微改了一下就ok了。至于解法2，就是用时间换了一部分空间。这个算法的时间复杂度因为节点数量是N所以是O（N），空间复杂度是O（N），在最差情况下，即当树为平衡二叉树时，最多N/2 个树节点同时在 queue 中，所以为O（N）。
class Solution:
def levelOrder1(self, root: TreeNode) -> List[int]:
if not root:
return []
queue, res = [root], []
while queue:
tmp = []
for node in queue:
res.append(node.val)
if node.left:
tmp.append(node.left)
if node.right:
tmp.append(node.right)
queue = tmp
return res
def levelOrder2(self, root: TreeNode) -> List[int]:
if not root:
return []
queue, res = [root], []
while queue:
node = queue.pop(0)
res.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return resPREVIOUSjz031.栈的压入、弹出序列
NEXTlc946.验证栈序列