102. 二叉树的层序遍历

leecode原题

题目

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

示例 1：

示例

示例 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

解题思路

思路

这套题是典型的层次遍历题，可以用作模板解决其它类型的问题。

该题的关键点在于: 层次遍历这种情况，我们需要借助队列实现即可。重点要诀: 每一次循环将该层元素全部送入队列后，记住当前队列队列长度，然后依次弹出队列元素(弹出队列长度N个元素), 并且在弹出元素的时候，将该元素的左右子树(判断非空)依次送入队列。更详细的可以看代码, 很容易就看明白了。

实现

源码

// 用数组实现个简单的队列功能
type Queue struct {
    elements []*TreeNode
}

func NewQueue() *Queue {
    return &Queue{elements: make([]*TreeNode, 0)}
}

func (q *Queue) Push(node *TreeNode) {
    q.elements = append(q.elements, node)
}

func (q *Queue) Pop() *TreeNode {
    if q.IsEmpty() {
        return nil
    }
    node := q.elements[0]
    q.elements = q.elements[1:]
    return node
}

func (q *Queue) Size() int {
    return len(q.elements)
}

func (q *Queue) IsEmpty() bool {
    if q.Size() == 0 {
        return true
    }
    return false
}

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    nodeArr := make([][]int, 0)
    q := NewQueue()
  // 头元素先送入队列
    q.Push(root)
    for !q.IsEmpty() {
        currentLevelNodeArr := make([]int, 0)
        qSize := q.Size() // 代表当前这一层的元素， 一定要先取出size, q.Size()会一直变化
        for i := 0; i < qSize; i++ {
            topNode := q.Pop()
            currentLevelNodeArr = append(currentLevelNodeArr, topNode.Val)
            // 将该节点的左右子树分别塞入队列中
            if topNode.Left != nil {
                q.Push(topNode.Left)
            }
            if topNode.Right != nil {
                q.Push(topNode.Right)
            }
        }
        if len(currentLevelNodeArr) != 0 {
            nodeArr = append(nodeArr, currentLevelNodeArr)
        }
    }
    return nodeArr
}