【LeetCode】102. 二叉树的层序遍历（错题2刷）

【LeetCode】102. 二叉树的层序遍历（错题2刷）

思路
层序遍历我们需要借助队列来辅助，整体思想就是根入队，然后d出入它的左右子树。一个问题是怎么知道每次出多少个队列元素，因为我们在出队的同时也在入队，因此解决这个问题的办法是针对每一层开始时，我们就先计算好它的原始长度。

type MyQueue struct {
    queue []*TreeNode
}

func NewQueue() *MyQueue {
    return &MyQueue{}
}

// 头出队
func (mq *MyQueue) pop() *TreeNode {
    if mq.isEmpty() {
        return nil
    }
    resNode := mq.queue[0]
    mq.queue = mq.queue[1 :]
    return resNode
}

// 入队
func (mq *MyQueue) push(node *TreeNode) {
    mq.queue = append(mq.queue, node)
}

func (mq *MyQueue) isEmpty() bool {
    if len(mq.queue) <= 0 {
        return true
    }
    return false
}

func levelOrder(root *TreeNode) [][]int {
    res := make([][]int, 0)
    if root == nil {
        return res
    }
    mq := NewQueue()
    mq.push(root)
    for !mq.isEmpty() {
        curLevel := []int{}
        curLen := len(mq.queue)
        for i := 0; i < curLen; i++ {
            popNode := mq.pop()
            if popNode == nil {
                break
            }
            curLevel = append(curLevel, popNode.Val)
            if popNode.Left != nil {
                mq.push(popNode.Left)
            }
            if popNode.Right != nil {
                mq.push(popNode.Right)
            }
        }
        res = append(res, curLevel)
    }
    return res
}