二叉树层次遍历

leetcode-二叉树层序遍历

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

    res := make([][]int, 0)
    // 使用slice来保存队列
    list := make([]*TreeNode, 0)
    // 从root节点开始
    list = append(list, root)
    listLen := len(list)

    for len(list) > 0 {
        // 下一层的数量
        nextLevelLen := 0
        // 本轮的结果
        path := make([]int, 0)

        // 每一层遍历
        for listLen > 0 {
            // 弹出一个节点
            node := list[0]
            listLen--
            path = append(path, node.Val)

            // 如果list只有一个元素，则重新初始化一下
            if len(list) == 0 {
                list = make([]*TreeNode, 0)
            } else {
                list = list[1:]
            }

            if node.Left != nil {
                list = append(list, node.Left)
                nextLevelLen++
            }

            if node.Right != nil {
                list = append(list, node.Right)
                nextLevelLen++
            }
        }

        // 遍历完成
        res = append(res, path)
        listLen = nextLevelLen
    }

    return res
}