102. 二叉树的层序遍历 中等

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

示例:
二叉树:[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果:

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

代码参考:

package main

import "fmt"

func main() {
    tree := &Tree{}
    tree.root = &TreeNode{Val: 4}
    for _, v := range []int{2, 7, 1, 3, 6, 9} {
        tree.BFSInsert(v)
    }
    fmt.Println(levelOrder(tree.root))
}

// 层次遍历(宽度优先遍历)
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    var res [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        var floor []int
        level := len(queue) // level 表示第几层,用于取出当前层的所有值
        for i := 0; i < level; i++ {
            cur := queue[0]
            queue = queue[1:]
            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
            floor = append(floor, cur.Val)
        }
        res = append(res, floor)
    }
    return res
}
最后编辑: kuteng  文档更新时间: 2021-06-05 10:16   作者:kuteng