📑 题目：102. 二叉树的层序遍历

🚀 本题 LeetCode 传送门

题目大意

按层序从上到下遍历一颗树。

解题思路

用一个队列即可实现。

代码

package leetcode
import (
 ""github.com/halfrost/LeetCode-Go/structures""
)
// TreeNode define
type TreeNode = structures.TreeNode
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// 解法一 BFS
func levelOrder(root *TreeNode) [][]int {
 if root == nil {
  return [][]int{}
 }
 queue := []*TreeNode{root}
 res := make([][]int, 0)
 for len(queue) > 0 {
  l := len(queue)
  tmp := make([]int, 0, l)
  for i := 0; i < l; i++ {
   if queue[i].Left != nil {
    queue = append(queue, queue[i].Left)
   }
   if queue[i].Right != nil {
    queue = append(queue, queue[i].Right)
   }
   tmp = append(tmp, queue[i].Val)
  }
  queue = queue[l:]
  res = append(res, tmp)
 }
 return res
}
// 解法二 DFS
func levelOrder1(root *TreeNode) [][]int {
 var res [][]int
 var dfsLevel func(node *TreeNode, level int)
 dfsLevel = func(node *TreeNode, level int) {
  if node == nil {
   return
  }
  if len(res) == level {
   res = append(res, []int{node.Val})
  } else {
   res[level] = append(res[level], node.Val)
  }
  dfsLevel(node.Left, level+1)
  dfsLevel(node.Right, level+1)
 }
 dfsLevel(root, 0)
 return res
}