102 二叉树的层序遍历

题目描述#

给你二叉树的根节点 root，返回其节点值的层序遍历结果，即逐层从左到右访问所有节点，每一层的节点值放在一个子数组中。

思路#

BFS 层序遍历的经典模板。用队列维护当前层的所有节点，每次循环开始时记录 queueSize，表示当前层的节点数，然后只处理这么多个节点，处理完一层后 height 自增，进入下一层。

每处理一个节点，就把它的值追加到 ans[height]，同时把左、右子节点加入队列备用。这样每一层处理完，ans 里就多了一个完整的子数组。

根节点为空时直接返回空数组，不进入循环。

代码#

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    queue := []*TreeNode{root}
    ans := [][]int{}
    height := 0
    for len(queue) > 0 {
        queueSize := len(queue)
        ans = append(ans, []int{})
        for i := 0; i < queueSize; i++ {
            node := queue[0]
            queue = queue[1:]
            ans[height] = append(ans[height], node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        height++
    }
    return ans
}