一、简介

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

二叉树：[3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：[3,9,20,15,7]

go语言 二叉树结构 如下：

type TreeNode struct {
   Val   int
   Left  *TreeNode
   Right *TreeNode
}

二、解决方案

2.1、利用队列

a.构建简单的队列，先进先出

type Queue struct {
   data []*TreeNode
}

func (q *Queue) Push(n *TreeNode) {
   if q.data == nil {
      q.data = make([]*TreeNode, 0)
   }

   q.data = append(q.data, n)
}

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

   node := q.data[0]
   q.data = q.data[1:]

   return node
}

b.利用队列层次遍历二叉树

func levelOrder(root *TreeNode) []int {
   rs := make([]int, 0)

   q := new(Queue)
   q.Push(root)

   for {
      curNode := q.Pop()
      if curNode == nil {
         break
      }

      rs = append(rs, curNode.Val)

      if curNode.Left != nil {
         q.Push(curNode.Left)
      }

      if curNode.Right != nil {
         q.Push(curNode.Right)
      }
   }

   return rs
}

c.测试

func main() {
   head := &TreeNode{
      Val:3,
      Left:&TreeNode{
         Val:9,
      },
      Right:&TreeNode{
         Val:20,
         Left:&TreeNode{
            Val:15,
         },
         Right:&TreeNode{
            Val:7,
         },
      },
   }

   data := levelOrder(head)
   fmt.Println(data)
}

三、层次遍历变种1

输出如下结构：

[
  [3],
  [9,20],
  [15,7]
]

相当于每层封装到一个数组里面，代码实现如下：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Queue struct {
	data []*TreeNode
}

func (q *Queue) Push(n *TreeNode) {
	if q.data == nil {
		q.data = make([]*TreeNode, 0)
	}

	q.data = append(q.data, n)
}

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

	node := q.data[0]
	q.data = q.data[1:]

	return node
}

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

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    q := new(Queue)
	q.Push(root)

	rs := make([][]int, 0)
	for q.Len() > 0 {
		// 当前层的个数为
		count := q.Len()

		curData := make([]int, 0) // 保存当前层级的元素
		// 取出当前层的节点，并将下一层节点插入队列
		for i:=0; i< count; i++ {
			curNode := q.Pop()
			if curNode.Left != nil {
				q.Push(curNode.Left)
			}

			if curNode.Right != nil {
				q.Push(curNode.Right)
			}

			curData = append(curData, curNode.Val)
		}

		rs = append(rs, curData)
	}

	return rs
}