剑指Offer（二十二）：从上往下打印二叉树
搜索微信公众号:’AI-ming3526’或者’计算机视觉这件小事’ 获取更多算法、机器学习干货
一、引子
这个系列是我在牛客网上刷《剑指Offer》的刷题笔记，旨在提升下自己的算法能力。
查看完整的剑指Offer算法题解析请点击：剑指Offer完整习题解析
二、题目
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
1、思路
这个题目其实是一个二叉树层级遍历的题。
举例子说明：
如上图所示，因为按层打印的顺序决定应该先打印根结点，所以我们从树的根结点开始分析。为了接下来能够打印值为8的结点的两个子结点，我们应该在遍历该结点时把值为6和10的两个结点保存到一个容器里，现在容器内就有两个结点了。按照从左到右打印的要求，我们先取出为6的结点。打印出值6之后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有三个结点，值分别为10、5和7。接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5、7的结点先放入容器，此时又比这两个结点先取出，这就是我们通常说的先入先出，因此不难看出这个数据容器应该是一个队列。由于值为5、7、9、11的结点都没有子结点，因此只要依次打印即可。
所以我们可以得出按层打印的方法是，每一次打印一个结点的时候，如果该结点有子结点，按照从左到右则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点，重复前面的打印操作，直至队列中所有的结点都打印出来为止。
2、编程实现
python
代码实现方案：
# -*- 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 not root:
return []
else:
currentStack1 = [root]
res = []
while currentStack1:
nextStack = []
for i in currentStack1:
if i.left : nextStack.append(i.left)
if i.right : nextStack.append(i.right)
res.append(i.val)
currentStack1 = nextStack
return res
AIMI-CN AI学习交流群【1015286623】 获取更多AI资料
分享技术，乐享生活：我们的公众号计算机视觉这件小事每周推送“AI”系列资讯类文章，欢迎您的关注！
