从上往下打印二叉树
从上往下打印二叉树
http://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701
题目：从上往下打印出二叉树的每个节点，同层节点从左至右打印。
首先这个用C++ 的队列实现是比较简单方便的，下面是python实现，定义了多个列表，比起C++要的队列要稍微麻烦点
思路：
（1）首先定义一个需要返回的列表 res
（2）每次遍历到有节点的时候都要插入节点值到res
（3）另外定义 nextlist 列表目的是保存下一层有节点的值
（4）等到下一层没有节点的时候，nextlist自然也就为空，跳出循环，返回res
def PrintFromTopToBottom(self, root):
if not root:
return []
res = []#最终的返回列表
# 先将root中的成员拷贝到新定义的 newroot中
newroot = [root]
while newroot:
nextlist = [] # 定义的下一个列表，每一次循环都要清空
for i in newroot:
# 存在左右孩子的话就插到nextlist 列表中
if i.left:
nextlist.append(i.left)
if i.right:
nextlist.append(i.right)
res.append(i.val)
newroot = nextlist
return res
腾讯音乐娱乐集团公司福利 108人发布
查看7道真题和解析