Description
有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树。
给定二叉树的根结点root,请返回打印结果,结果按照每一层一个数组进行储存,所有数组的顺序按照层数从上往下,且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
Solutions
1. Queue
但如果是要按照每层存为一个数组的方式打印(分层打印),上述的方式就没有办法实现了。难点在于如何知道换行,可以采用两个指针的方式来实现:
- last:表示正在打印的当前行的最右节点
- 当遍历到 last 结点说明要换行了
- 换行时需要将 last = next_last
- next_last:表示下一行的最右节点
- 一直跟踪 queue 新加入的结点即可,因为 queue 最新加入的结点一定是目前发现的下一层最右的节点
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class TreePrinter:
def printTree(self, root):
# write code here
if root is None:
return []
res = []
queue = [root]
level = []
last = next_last = root
while queue:
node = queue.pop()
level.append(node.val)
if node.left:
queue.insert(0, node.left)
next_last = node.left
if node.right:
queue.insert(0, node.right)
next_last = node.right
if node == last:
last = next_last
res.append(level)
level = []
return res
1.1 简单地自上而下打印
直接广度优先遍历,用 queue 实现既可:
# -*- coding:utf-8 -*-
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# 返回从上到下每个节点值列表,例:[1,2,3]
def PrintFromTopToBottom(self, root):
# write code here
if root is None:
return []
res = []
queue = [root]
while queue:
node = queue.pop()
res.append(node.val)
if node.left:
queue.insert(0, node.left)
if node.right:
queue.insert(0, node.right)
return res
# 运行时间:34ms
# 占用内存:5856k