目录
二叉树Z形遍历
访问量:70

一、题目

给定一个二叉树,返回该二叉树的之字形层序遍历,(第一层从左向右,下一层从右向左,一直这样交替)

题目来源:牛客

二、实现

和“二叉树层级遍历升级版”很像,需要加个变量控制一下方向即可。实现如下:

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * @param pRoot TreeNode类
 * @return int整型二维数组
 */
func Print(pRoot *TreeNode) [][]int {
   if pRoot == nil {
      return nil
   }
   // write code here
   stackData := new(Stack)
   stackData.add(pRoot)

   res := make([][]int, 0)
   direction := true // 控制方向
   childStack := new(Stack)
   curRes := make([]int, 0)
   for {
      curNode := stackData.pop()
      if curNode == nil {
         stackData, childStack = childStack,stackData

         res = append(res, curRes)
         curRes = make([]int, 0)

         direction = !direction

         curNode = stackData.pop()
      }

      if curNode == nil {
         break
      }

      curRes = append(curRes, curNode.Val)

      if direction {
         // 先右后左
         if curNode.Left != nil {
            childStack.add(curNode.Left)
         }

         if curNode.Right != nil {
            childStack.add(curNode.Right)
         }
      } else {
         // 先左后右
         if curNode.Right != nil {
            childStack.add(curNode.Right)
         }

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

   return res
}