二叉树的层序遍历（python）

本文主要是介绍二叉树的层序遍历（python），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指offer：从上到下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

结果：[8,6,10,5,7,9,11]

解题思路

典型的使用队列的题目。每从队列头部获取一个节点，就将该节点的左右子节点存入队列的尾部。如此往复，直至队列为空。 

代码

#coding:utf-8
class Solution:#从上往下打印出二叉树的每个节点，同层节点从左至右打印def PrintFromTopToBottom(self, root):array = []result = []if root == None:return resultarray.append(root)while array:newNode = array.pop(0)result.append(newNode.val)if newNode.left != None:  array.append(newNode.left)if newNode.right != None:array.append(newNode.right)return result# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':flag = "printTreeNode"solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)if flag == "printTreeNode":newArray = solution.PrintFromTopToBottom(treeRoot1)print(newArray)

leetcode---102. Binary Tree Level Order Traversal

#coding:utf-8class Solution:#从上往下打印出二叉树的每个节点，同层节点从左至右打印def levelOrder(self, root):array = []result = []if root == None:return resultarray.append(root)while array:templist = []for i in range(len(array)):newNode = array.pop(0)templist.append(newNode.val)if newNode.left != None:array.append(newNode.left)if newNode.right != None:array.append(newNode.right)result.append(templist)return result# 给定二叉树的前序遍历和中序遍历，获得该二叉树def getBSTwithPreTin(self, pre, tin):if len(pre)==0 | len(tin)==0:return Noneroot = treeNode(pre[0])for order,item in enumerate(tin):if root .val == item:root.left = self.getBSTwithPreTin(pre[1:order+1], tin[:order])root.right = self.getBSTwithPreTin(pre[order+1:], tin[order+1:])return rootclass treeNode:def __init__(self, x):self.left = Noneself.right = Noneself.val = xif __name__ == '__main__':flag = "printTreeNode"solution = Solution()preorder_seq = [1, 2, 4, 7, 3, 5, 6, 8]middleorder_seq = [4, 7, 2, 1, 5, 3, 8, 6]treeRoot1 = solution.getBSTwithPreTin(preorder_seq, middleorder_seq)if flag == "printTreeNode":newArray = solution.levelOrder(treeRoot1)print(newArray)

leetcode和剑指offer不同之处是输出的格式，也很好解决，细心一下就好。

[[1], [2, 3], [4, 5, 6], [7, 8]]

这篇关于二叉树的层序遍历（python）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---