题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
Solutions
采用广度优先遍历的方式写了如下的代码：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if pRoot is None:
return []
queue = [pRoot]
res = []
while queue:
level = []
size = len(queue)
for i in range(size):
node = queue.pop(0)
level.append(node.val)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
res.append(level)
return res
# 运行时间：28ms
# 占用内存：5792k
还有另一种类似的解决办法：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot:
return []
res=[]
arr=[]
arr.append(pRoot)
cur=0
#last=1
while cur<len(arr):
last=len(arr)
temp=[]
while (cur<last):
temp.append(arr[cur].val)
if arr[cur].left:
arr.append(arr[cur].left)
if arr[cur].right:
arr.append(arr[cur].right)
cur+=1
res.append(temp)
return res
# 运行时间：25ms
# 占用内存：5732k
剑指 offer 上的解法稍显复杂：
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回二维列表[[1,2],[4,5]]
def Print(self, pRoot):
# write code here
if not pRoot:
return []
res=[]
res_val=[]
res.append(pRoot)
nextLevel=0 #表示下一层节点的数目
toBePrinted=1 #表示当前层还没有打印的节点数
temp=[]
while len(res)>0:
node=res[0]
temp.append(node.val)
if node.left:
res.append(node.left)
nextLevel+=1
if node.right:
res.append(node.right)
nextLevel+=1
del res[0]
toBePrinted-=1
if toBePrinted==0:
res_val.append(temp)
toBePrinted=nextLevel
nextLevel=0
temp=[]
return res_val
# 运行时间：42ms
# 占用内存：5736k