一、题目

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）

例如：

给定的二叉树是{1-2-5-7-4-6}

需要输出：[[1],[3,5],[7,4,6]]

二、解法

思路：如果简单的层级遍历，直接使用队列实现就行，如果要输出每层一个数组，两个队列就行。

队列实现如下

// 先进先出
type Queue struct {
   data []*TreeNode
}

// 插入到最后
func (s *Queue) add(d *TreeNode) {
   if s.data == nil {
      s.data = make([]*TreeNode, 0)
   }

   s.data = append(s.data, d)
}

func (s *Queue) pop() *TreeNode {
   if len(s.data) == 0 {
      return nil
   }

   curNode := s.data[0]

   s.data = s.data[1:]

   return curNode
}

func (s *Queue) len() int {
   return len(s.data)
}

算法实现如下：

/**
 *
 * @param root TreeNode类
 * @return int整型二维数组
 */
func levelOrder(root *TreeNode) [][]int {
   // write code here
   if root == nil {
      return nil
   }

   res := make([][]int, 0)

   curQueue := new(Queue)
   curQueue.add(root)

   for curQueue.len() != 0 {
      curLayQueue := new(Queue) // 存储下一层节点
      curLayVal := make([]int, 0)
      curNode := curQueue.pop()
      for  curNode != nil {
         curLayVal = append(curLayVal, curNode.Val)

         if curNode.Left != nil {
            curLayQueue.add(curNode.Left)
         }

         if curNode.Right != nil {
            curLayQueue.add(curNode.Right)
         }

         curNode = curQueue.pop()
      }

      // 将当前层的所有节点以数组形式，放到返回值中
      res = append(res, curLayVal)

      // 将下一层节点，都放到，当前队列中
      curQueue = curLayQueue
   }

   return res
}

题目来源：牛客