剑指Offer32-2 从上到下打印二叉树2Golang版

  

剑指Offer32-2 从上到下打印二叉树2Golang版

1. 问题描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回其层次遍历结果：

[
[3],
[9,20],
[15,7]
]

提示：

节点总数 <= 1000

2. 思路

  1. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。

  2. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。

作者：jyd
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/solution/mian-shi-ti-32-ii-cong-shang-dao-xia-da-yin-er-c-5/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3. 代码

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

    queue := []*TreeNode{root}

    for len(queue) > 0 {
        length := len(queue)
        layer := make([]int, 0)
        // length控制每一层的个数，每次出队列的个数为本层的元素length个
        for length > 0 {
            if queue[0].Left != nil {
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                queue = append(queue, queue[0].Right)
            }
            layer = append(layer, queue[0].Val)
            queue = queue[1:]
            length--
        }
        res = append(res, layer)
    }
    
    return res
}
相关文章
开发语言最新文章
热门教程