题目描述:从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
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