好的，按照bfs写了一下自己朴素的解法，就很简单了，不用多说了吧。当然别人还有更加好一点的实现，如解法2所示。这个算法的时间复杂度是O（N），空间复杂度是O（N）。
class Solution:
def levelOrder1(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue, res = [root], [[root.val]]
while queue:
tmpnode = []
tmpval = []
for node in queue:
if node.left:
tmpnode.append(node.left)
tmpval.append(node.left.val)
if node.right:
tmpnode.append(node.right)
tmpval.append(node.right.val)
if tmpval:
res.append(tmpval)
queue = tmpnode
return res
def levelOrder2(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue, res = [root], []
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.pop(0)
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return res
def levelOrder3(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
queue, res = [root], []
while queue:
tmp = []
for _ in range(len(queue)):
node = queue.pop(0)
tmp.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(tmp)
return resPREVIOUSlc946.验证栈序列