LeetCode 0102.二叉树的层序遍历

二叉树的层序遍历

LeetCode102. 二叉树的层序遍历

题目描述

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

思路

题目要求

给定一个二叉树的根节点，层次遍历该二叉树
返回其节点值的层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。

队列先进先出，符合一层一层遍历的逻辑

代码

Go

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    // 用切片存储遍历节点数值
    res := make([][]int, 0)
    if root == nil {
        // 根节点为空
        return res
    }
    // 用切片模拟队列
    queue := make([]*TreeNode, 0)
    // 根节点入队
    queue = append(queue, root)
    // 遍历二叉树
    for len(queue) > 0 {
        // 记录当前层节点数
        l := len(queue)
        // 用临时切片存储每层节点的数值
        tempSlice := make([]int, 0)
        // 遍历一层
        for i := 0; i < l; i++ {
            // 若当前节点有子节点,则入队
            if queue[0].Left != nil {
                // 左子节点入队
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                // 右子节点入队
                queue = append(queue, queue[0].Right)
            }
            // 记录当前节点值
            tempSlice = append(tempSlice, queue[0].Val)
            // 当前节点出队
            queue = queue[1:]
        }
        // 将一层的节点值存入结果集
        res = append(res, tempSlice)
    }
    return res
}

Link

GitHub