给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
python
# 0102.二叉树的层序遍历
class Solution:
def levelOrder(self, root: TreeNode) -> [[int]]:
"""
迭代法：双端队列，每次把单层的节点遍历出队列，另外将对应的左右节点加入队列
:param root:
:return:
"""
results = []
if not root:
return results
from collections import deque
queue = deque([root]) # 初始化队列
while queue:
size = len(queue) # 遍历队列单层长度
res = [] # 每次遍历时初始化加入结果集中的列表
for _ in range(size):
cur = queue.popleft() # 通过size控制遍历次数
res.append(cur.val) # 加入结果集中
if cur.left: # 添加当前pop节点的左节点进入队列
queue.append(cur.left)
if cur.right: # 添加当前pop节点的右节点进入队列
queue.append(cur.right)
results.append(res) # 当层中的所有节点的值放入list中
return results
def levelOrderRecur(self, root: TreeNode) -> [[int]]:
"""
递归法，
:param root:
:return:
"""
res = []
def levelOrder(node, index):
if not node: # 空，返空
return []
if len(res) < index: # 开始当前depth
res.append([])
res[index-1].append(node.val) # 当前层加入节点值到结果集
if node.left: # 当前节点有左节点，继续递归，同时层数加1
levelOrder(node.left, index+1)
if node.right: # 当前节点有右节点，继续递归，同时层数加1
levelOrder(node.right, index+1)
levelOrder(root, 1) # 1层开始递归
return res
golang
package binaryTree
import "container/list"
// 递归遍历
func levelOrderRecur(root *TreeNode) [][]int {
var levelOrder func(node *TreeNode, depth int)
var res [][]int
levelOrder = func(node *TreeNode, depth int) {
if node == nil {
return
}
if len(res) == depth {
res = append(res, []int{})
}
res[depth] = append(res[depth], node.Val)
if node.Left != nil {
levelOrder(node.Left, depth+1)
}
if node.Right != nil {
levelOrder(node.Right, depth+1)
}
}
levelOrder(root, 0)
return res
}
// 迭代遍历
func levelOrderiteration(root *TreeNode) [][]int {
var res = [][]int{}
if root == nil { // 空时返回
return res
}
queue := list.New() // 队列初始化
queue.PushBack(root)
var tmpArr []int
for queue.Len() > 0 {
length := queue.Len()
for i:=0;i<length;i++ { // 遍历当层的节点
node := queue.Remove(queue.Front()).(*TreeNode) // 当次节点
if node.Left != nil { // 节点的左节点入队
queue.PushBack(node.Left)
}
if node.Right != nil { // 节点的右节点入队
queue.PushBack(node.Right)
}
tmpArr = append(tmpArr, node.Val) // 节点值加入结果集
}
res = append(res, tmpArr)
tmpArr = []int{}
}
return res
}