题解 | #求二叉树的层序遍历# （不懂就多看几遍！加油）

package main

import (
	. "nc_tools"
)

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
  //1、先将根节点入队，根节点一定是第一层
	var q = &Queue{}
    q.Enqueue(root)
  
    var res = make([][]int, 0)
  //2、将元素按照层级依次放入队列，队列为空时退出
    for len(q.items) >0 {
	  
	  //3、每次暂存下一层的子节点，等本层遍历完成后，再将子节点入依次队
        var arr = make([]int, 0) // 每层的结果
        var nodeArr = make([]*TreeNode, 0) // 用来暂存子节点
        for {
            var peek = q.Dequeue()
            if peek == nil {
                break
            }
            if peek.Left != nil {
                 nodeArr = append(nodeArr, peek.Left)
            }
            if peek.Right != nil {
                 nodeArr = append(nodeArr, peek.Right)
            }
		  //4、遍历队列，获取本层节点，队列为空时，本层遍历完成。
             arr = append(arr, peek.Val)
        }
        res = append(res, arr)
	  // 5、下层子节点入队
        for _, node := range nodeArr {
            q.Enqueue(node)
        }

    }

    return res
}

// 实现一个简单队列
type Queue struct {
	items []*TreeNode
}

func (q *Queue) Enqueue(item *TreeNode) {
	q.items = append(q.items, item)
}

func (q *Queue) Dequeue() *TreeNode {
	if len(q.items) == 0 {
		return nil
	}
	item := q.items[0]
	q.items = q.items[1:]
	return item
}