102. 二叉树的层序遍历

题目

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

难度：🌟🌟

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

题解

通过 for !queue.isEmpty() 循环控制从上到下一层层遍历， for i := 0; i < len(queue); i++ 控制每一层从左向右遍历。

代码实现

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int     // 保存每层节点
	queue := newQueue() // 使用队列保存
	queue.offer(root)
	for !queue.isEmpty() {
		var ans []int // 当前层元素值
		sz := queue.len()
		for sz > 0 {
			// 弹出队头元素
			top := queue.pop()
			ans = append(ans, top.Val)
			if top.Left != nil {
				queue.offer(top.Left)
			}
			if top.Right != nil {
				queue.offer(top.Right)
			}
			sz--
		}
		res = append(res, ans)
	}
	return res
}

type myQueue struct {
	data []*TreeNode
}

func newQueue() *myQueue {
	return &myQueue{}
}

func (q *myQueue) offer(elem *TreeNode) {
	q.data = append(q.data, elem)
}

func (q *myQueue) pop() *TreeNode {
	res := q.data[0]
	q.data = q.data[1:]
	return res
}

func (q *myQueue) len() int {
	return len(q.data)
}

func (q *myQueue) isEmpty() bool {
	return q.len() == 0
}