python-leetcode40.二叉树的层序遍历

题目：

给定二叉树的根节点root,返回其节点值得层序遍历（即逐层从左到右访问所有节点）

---

 方法：广度优先搜索

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def levelOrder(self, root): """ :type root: Optional[TreeNode] :rtype: List[List[int]] """ if root is None: #树为空,返回空列表 return [] ans=[] #存储最终的结果，初始化为空列表 cur=[root] #正在处理的节点列表（从根节点开始） while cur: #当前层还有未处理的节点 nxt=[] #存储下一层的节点 vals=[] #当前层的节点值 for node in cur: vals.append(node.val) if node.left: #当前节点有左子树（node.left），将左子节点添加到 nxt 列表 nxt.append(node.left) if node.right: #当前节点有右子树（node.right），将右子节点添加到 nxt 列表 nxt.append(node.right) cur=nxt #将下一层的节点赋给 cur，准备进入下一轮循环 ans.append(vals) #将当前层的节点值vals添加到 ans 列表中，表示这一层的值已经完成处理 return ans

时间复杂度：O(n)

空间复杂度：O(n)

# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution(object): def levelOrder(self, root): """ :type root: Optional[TreeNode] :rtype: List[List[int]] """ ret=[] #用于存储最终的层序遍历结果 if root is None: return ret queue=[] queue.append(root) while queue: #只要队列中有节点，继续进行层序遍历 level=[] #用于存储当前层所有节点的值 currentLevelSize=len(queue) for i in range(currentLevelSize): #获取当前队列中节点的数量，也就是当前层的节点数量 node=queue.pop(0) #每次循环从队列中弹出一个节点 level.append(node.val) #将节点的值 node.val 添加到 level 列表中 if node.left is not None: #如果节点有左子树，将左子节点 node.left 加入队列 queue.append(node.left) if node.right is not None: #如果节点有右子树，将右子节点 node.right 加入队列 queue.append(node.right) ret.append(level) #当前层的所有节点值存入 level 列表中 return ret

时间复杂度：O(n)

空间复杂度：O(n)