python | #求二叉树的层序遍历#

NC15 求二叉树的层序遍历

日期：2021.9.2

二叉树的三种遍历方法：python 二叉树 前序中序后序层序 递归与非递归遍历_Mario的博客-CSDN博客

前序遍历：中左右（先读当前节点的值，然后跳到左边，和右边）

中序遍历：左中右

后序遍历：左右中

层序遍历

初步思路：使用一个队列来存储每一层的所有树节点，然后遍历队列中节点的所有值，并用一个临时队列，遍历原队列中节点的所有子节点，将原队列更新为临时队列

时间复杂度：O (N) 空间复杂度O（N）

缺点：使用了一个临时队列，可以优化后将其去掉

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root ):
        # write code here
        if root is None:
            return []
        queue = [root] #遍历存储某一层的所有节点
        res = [] #返回结果
        while len(queue)>0:#当某一层节点数量为零时，跳出循环
            res.append([node.val for node in queue])#遍历所有值
            temp = [] #临时列表存储下一层节点
            for node in queue: #注意从左向右添加节点
                if node.left is not None:
                    temp.append(node.left)
                if node.right is not None:
                    temp.append(node.right)
            queue = temp
        return res

参考：递归解法：

class Solution:
    def levelOrder(self , root ):
        # write code here
        if root is None:
            return []
        res = [] # 返回值
        level = 0 #保存层数
        def get_level(level,node):
            if level == len(res):#当遍历到下一层时，添加一层
                res.append([])
            res[level].append(node.val) #将值添加到对应的层
            if node.left:
                get_level(level+1,node.left) #进入下一层的左侧
            if node.right:
                get_level(level+1,node.right)#进入下一层的右侧
        get_level(level,root)
        return res