目录
二叉树层级遍历升级版
访问量:941

一、题目

给定一个二叉树,返回该二叉树层序遍历的结果,(从左到右,一层一层地遍历)

例如:

给定的二叉树是{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
}


题目来源:牛客