102.levelOrder.go

package tree

// BFS 普通的BFS遍历
funcBFS(root*TreeNode) []int { // {{{
varres []int
varqueue []*TreeNode= []*TreeNode{root}
ifroot==nil {
returnres
 }

forlen(queue) >0 {
node:=queue[0]
res=append(res, node.Val)
queue=queue[1:]

ifnode.Left!=nil {
queue=append(queue, node.Left)
 }

ifnode.Right!=nil {
queue=append(queue, node.Right)
 }
 }
returnres
} // }}}

// 1. 普通的BFS 比较简单 只需要什么一个[]int 一个存放tree的队列 利用queue先进先出的规则打印value即可
// 2. 如果根据等级来保存[][]int的话 只要声明一个正在遍历的队列 一个保存下一层节点的队列即可
funclevelOrder1(root*TreeNode) [][]int { // {{{
varres [][]int
ifroot==nil {
returnres
 }

varqueue []*TreeNode= []*TreeNode{root}
forlen(queue) >0 {
vartmpQueue []*TreeNode
vartmpRes []int
forlen(queue) >0 {
node:=queue[0]
queue=queue[1:]

tmpRes=append(tmpRes, node.Val)
ifnode.Left!=nil {
tmpQueue=append(tmpQueue, node.Left)
 }
ifnode.Right!=nil {
tmpQueue=append(tmpQueue, node.Right)
 }
 }
queue=queue[0:0]
queue=append(queue, tmpQueue...)
res=append(res, tmpRes)
 }

returnres
} // }}}

// 递归大法
funclevelOrder2(root*TreeNode) [][]int {
varres [][]int
vardfsfunc(*TreeNode, int)

dfs=func(root*TreeNode, levelint) {
ifroot==nil {
return
 }
// 出现了新的level
iflevel>=len(res) {
res=append(res, []int{})
 }
res[level] =append(res[level], root.Val)

dfs(root.Left, level+1)
dfs(root.Right, level+1)
 }

dfs(root, 0)
returnres
}