把二叉树打印成多层[层次搜索]、以及之字形打印
2018-08-28 本文已影响0人
小歪与大白兔
题目一:
从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
# -*- 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 []
result = []#存储最终的输出结果
currentstack = [pRoot] # 存储当前层入栈的节点
while currentstack:
res = [] #存储该层的结果
nextstack = [] #存储下一层入栈的节点
for i in currentstack:
res.append(i.val)
if i.left:
nextstack.append(i.left)
if i.right:
nextstack.append(i.right)
currentstack = nextstack
result.append(res)
return result
题目二:
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
思路:只需在上一题中新增一个time用来记录当前是奇数层还是偶数层即可;如果是偶数层,则将res中的元素反转:res.reverse()或者是res = res[::-1]
# -*- 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 []
result = []#存储最终的输出结果
currentstack = [pRoot] # 存储当前层入栈的节点
time = 0
while currentstack:
res = [] #存储该层的结果
nextstack = [] #存储下一层入栈的节点
time += 1
for i in currentstack:
res.append(i.val)
if i.left:
nextstack.append(i.left)
if i.right:
nextstack.append(i.right)
currentstack = nextstack
if time % 2== 0:
res.reverse()
result.append(res)
return result