二叉树的层序遍历
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。
而go语言中的库函数中没有定义好的栈，只有双向链表。由由于go语言的切片是值传递，并不是引用传递，所以我们可以通过闭包来解决这个问题。
闭包
所谓闭包就是一个函数“捕获”了和它在同一作用域的其它常量和变量。这就意味着当闭包被调用的时候，不管在程序什么地方调用，闭包能够使用这些常量或者变量。它不关心这些捕获了的变量和常量是否已经超出了作用域，所以只有闭包还在使用它，这些变量就还会存在。
在 Go 语言里，所有的匿名函数(Go 语言规范中称之为函数字面量)都是闭包。匿名函数是指不需要定义函数名的一种函数实现方式。
// squares 返回一个匿名函数，func() int
// 该匿名函数每次被调用时都会返回下一个数的平方。
func squares() func() int {
var x int
return func() int {//匿名函数
x++ //捕获外部变量，闭包还在使用所以x的作用域并没有被释放
return x * x
}
}
func main() {
f := squares() //squares() 函数返回的是一个闭包，但是在这个语句中，你只给闭包赋值，并没有执行这个闭包函数。
fmt.Println(f()) // "1"，执行闭包
fmt.Println(f()) // "4"
fmt.Println(f()) // "9"
fmt.Println(f()) // "16"
}
层序遍历
/**
102. 二叉树的递归遍历
*/
func levelOrder(root *TreeNode) [][]int {
arr := [][]int{}
depth := 0
var order func(root *TreeNode, depth int)
order = func(root *TreeNode, depth int) {
if root == nil {
return
}
if len(arr) == depth {
arr = append(arr, []int{})
}
arr[depth] = append(arr[depth], root.Val)
order(root.Left, depth+1)
order(root.Right, depth+1)
}
order(root, depth)
return arr
}
/**
102. 二叉树的层序遍历：使用切片模拟队列，易理解
*/
func levelOrder(root *TreeNode) (res [][]int) {
if root == nil {
return
}
curLevel := []*TreeNode{root} // 存放当前层节点
for len(curLevel) > 0 {
nextLevel := []*TreeNode{} // 准备通过当前层生成下一层
vals := []int{}
for _, node := range curLevel {
vals = append(vals, node.Val) // 收集当前层的值
// 收集下一层的节点
if node.Left != nil {
nextLevel = append(nextLevel, node.Left)
}
if node.Right != nil {
nextLevel = append(nextLevel, node.Right)
}
}
res = append(res, vals)
curLevel = nextLevel // 将下一层变成当前层
}
return
}
