2021-10-06：二叉树的锯齿形层序遍历。给定一个二叉树，返回其节点值的锯齿形层序遍历

2021-10-06：二叉树的锯齿形层序遍历。给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。力扣103。

福大大 答案2021-10-06：

自然智慧即可。层次遍历。 时间复杂度：O(N)。 空间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    head := &TreeNode{}
    head.val = 3

    head.left = &TreeNode{}
    head.left.val = 9
    head.right = &TreeNode{}
    head.right.val = 20

    head.right.left = &TreeNode{}
    head.right.left.val = 15
    head.right.right = &TreeNode{}
    head.right.right.val = 7

    ret := zigzagLevelOrder(head)
    fmt.Println(ret)
}

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
    ans := make([][]int, 0)
    if root == nil {
        return ans
    }
    deque := make([]*TreeNode, 0)
    deque = append(deque, root)
    size := 0
    isHead := true
    for len(deque) > 0 {
        size = len(deque)
        curLevel := make([]int, 0)
        for i := 0; i < size; i++ {
            var cur *TreeNode
            if isHead {
                cur = deque[0]
                deque = deque[1:]
            } else {
                cur = deque[len(deque)-1]
                deque = deque[0 : len(deque)-1]
            }
            curLevel = append(curLevel, cur.val)
            if isHead {
                if cur.left != nil {
                    deque = append(deque, cur.left)
                }
                if cur.right != nil {
                    deque = append(deque, cur.right)
                }
            } else {
                if cur.right != nil {
                    deque = append([]*TreeNode{cur.right}, deque...)
                }
                if cur.left != nil {
                    deque = append([]*TreeNode{cur.left}, deque...)
                }
            }
        }
        ans = append(ans, curLevel)
        isHead = !isHead
    }
    return ans
}

执行结果如下：

左神java代码