四时宝库

刚和儿子干了一架，打完后，继续练习算法，今天要实现的是二叉树锯齿层序遍历算法
题目要求如下：给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

我的实现代码如下，搭配另外一个数组翻转算法

package main

import (
    "fmt"
    "testing"
)

// TreeNode represents a node in a binary tree
type (
    TreeDocument struct {
       Val   int
       Left  *TreeDocument
       Right *TreeDocument
    }
)

// 实现一个数组翻转的快速算法，双指针移动实现快速交换
func revereArr(arr []int) []int {
    left, right := 0, len(arr)-1
    for left < right {
       arr[left], arr[right] = arr[right], arr[left]
       left++
       right--
    }
    return arr
}

// 二叉树遍历，先层序遍历，然后在利用上面方法实现快速翻转
func loopJcLayerArr(root *TreeDocument) [][]int {

    result := make([][]int, 0)
    queues := []*TreeDocument{root}
    switchFlg := true

    for len(queues) > 0 {
       queueSize := len(queues)
       layerArr := make([]int, queueSize)
       for i := 0; i < queueSize; i++ {
          queue := queues[0]
          layerArr[i] = queue.Val
          if queue.Left != nil {
             queues = append(queues, queue.Left)
          }
          if queue.Right != nil {
             queues = append(queues, queue.Right)
          }
          queues = queues[1:]
       }

       if switchFlg {
          result = append(result, layerArr)
       } else {
          result = append(result, revereArr(layerArr))
       }

       switchFlg = !switchFlg
    }

    return result
}

func TestJcLayerLoop(t *testing.T) {
    // 构建一个示例二叉树
    root := &TreeDocument{
       Val: 3,
       Left: &TreeDocument{
          Val: 9,
          Left: &TreeDocument{
             Val: 7,
          },
          Right: &TreeDocument{
             Val: 10,
          },
       },
       Right: &TreeDocument{
          Val: 20,
          Left: &TreeDocument{
             Val: 15,
             Left: &TreeDocument{
                Val: 11,
             },
             Right: &TreeDocument{
                Val: 16,
             },
          },
          Right: &TreeDocument{
             Val: 30,
             Left: &TreeDocument{
                Val: 23,
             },
             Right: &TreeDocument{
                Val: 33,
             },
          },
       },
    }

    result := loopJcLayerArr(root)
    fmt.Println("result => ", result)
}