二叉树的层序遍历

1. 题目描述

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

2. 思路

1. 思路一
   • 层序遍历就是一行行遍历
   • 本质上就是BFS，BFS需要用到队列
   • 层序遍历需要知道什么时候遍历完当前行，因此需要一个变量记录当前行的最后一个节点；
   • 同时还需要一个变量记录下一行的最后一个节点，以便更新
2. 思路二
   • 层序遍历就是一行行遍历
   • 本质上就是BFS，BFS需要用到队列
   • 在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点

3. 实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }


    allPaths := make([][]int, 0)
    path := make([]int, 0)
    queue := make([]*TreeNode, 0)
    queue = append(queue, root)
    currentLineLast := root
    var nextLineLast *TreeNode
    for len(queue) > 0 {
        root := queue[0]
        queue = queue[1:]

        path = append(path, root.Val)
        if root.Left != nil {
            queue = append(queue, root.Left)
            nextLineLast = root.Left
        }
        if root.Right != nil {
            queue = append(queue, root.Right)
            nextLineLast = root.Right
        }

        if root == currentLineLast {
            allPaths = append(allPaths, path)
            path = make([]int, 0)
            currentLineLast = nextLineLast
        }
    }


    return allPaths

}

4. 参考

• BFS 的使用场景总结：层序遍历、最短路径问题 - 二叉树的层序遍历 - 力扣（LeetCode）