算法篇：树之树的层次遍历
算法：
树的层次遍历是树的基本操作之一，包括二叉树的层次遍历，多叉树的层次遍历，以及二叉树层次遍历的变形题目，层次遍历+每一层的节点的翻转等操作。
对于这类题目，典型算法就是先将树按照层次存入数组当中，然后统一对每一层的数据进行数据处理。
题目1:
102. 二叉树的层序遍历
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
代码实现：
/**Definition for a binary tree node.type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode}*/:非递归操作*//*func levelOrder(root *TreeNode) [][]int {if root == nil {return nil}var stack []*TreeNodevar result [][]intstack = append(stack,root)for {if len(stack) == 0 {break;}:= helper(stack)if len(res) != 0 {result = append(result,res)}stack = stack1}return result}func helper(stack []*TreeNode)(res []int, stackRes []*TreeNode){if len(stack) == 0{return}for i:=0;i<len(stack); i++{node := stack[i]if node == nil {continue}res = append(res,node.Val)stackRes = append(stackRes,node.Left)stackRes = append(stackRes,node.Right)}return}*//*解法：队列来操作，树的层次遍历，从左到右遍历树的每一层存入对应的数组即可*//*:递归操作利用二叉树的先序遍历方法，也就是先访问根节点，在访问做左孩子，然后访问右孩子。*/func levelOrder(root *TreeNode) [][]int {return preOrder(root, 0, [][]int{})}func preOrder(root *TreeNode, level int, res [][]int) [][]int {if root == nil {return res}1.根节点的处理这里因为level从0开始计算的缘故，len放进去值之后就是1，所以==的时候，便是是新的一层开始if level == len(res) {res = append(res,[]int{root.Val})else {= append(res[level],root.Val)}2.左孩子节点的处理res = preOrder(root.Left,level+1,res)3.右孩子节点的处理res = preOrder(root.Right,level+1,res)return res}
执行结果：
题目2:
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
代码实现：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func levelOrderBottom(root *TreeNode) [][]int {r := [][]int{}order(root,0,&r)for i,j:= 0, len(r)-1;i<j;{r[i],r[j] = r[j],r[i]i++j--}return r}func order(root *TreeNode,level int,res *[][]int) {if root == nil {return}if len(*res)-1 < level {*res = append(*res,[]int{root.Val})} else {(*res)[level] = append((*res)[level],root.Val)}order(root.Left,level+1,res)order(root.Right,level+1,res)return}
执行结果：
题目3:
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
代码实现：
/*** Definition for a binary tree node.* type TreeNode struct {* Val int* Left *TreeNode* Right *TreeNode* }*/func zigzagLevelOrder(root *TreeNode) [][]int {if root == nil {return nil}res := [][]int{}levelOrder(root,0, &res)for i:=0; i< len(res); i++ {if i%2 == 1{j,k:=0,len(res[i])-1for j < k{res[i][j],res[i][k] = res[i][k],res[i][j]j++k--}}}return res}func levelOrder(root *TreeNode, l int, res *[][]int) {if root == nil {return}if len(*res)-1 < l {*res = append(*res,[]int{root.Val})} else {(*res)[l] = append((*res)[l],root.Val)}levelOrder(root.Left,l+1,res)levelOrder(root.Right,l+1,res)return}// 需要: 先按照层次去遍历存储，然后统一的做整理，调整需要转换的对应层次
结果输出：
题目4.
https://leetcode-cn.com/problems/n-ary-tree-level-order-traversal/
代码实现：
/*** Definition for a Node.* type Node struct {* Val int* Children []*Node* }*/func levelOrder(root *Node) [][]int {if root == nil {return nil}res := [][]int{}levelOrderOk(root,0,&res)return res}func levelOrderOk(root *Node,l int, res *[][]int){if len(*res)-1 < l {*res = append(*res,[]int{root.Val})} else {(*res)[l] = append((*res)[l],root.Val)}for _,t := range root.Children {levelOrderOk(t,l+1,res)}return}
执行结果：
本文分享自微信公众号 - 灰子学技术（huizixueguoxue）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
