103. 二叉树的锯齿形层序遍历

Link

103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）力扣 LeetCode

Problem

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

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

示例2：

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

示例3:

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

提示：

• 树中节点数目在范围 [0, 2000] 内

• -100 <= Node.val <= 100

Solution

Go

func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int(nil)
    }

    reverse := func(a []int) {
        n := len(a)
        for i := 0; i < n>>1; i++ {
            a[i], a[n-i-1] = a[n-i-1], a[i]
        }
    }

    ans := [][]int{}
    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {
        tmp := q 
        q = nil
        nums := []int{}
        for _, node := range tmp {
            nums = append(nums, node.Val)
            if node.Left != nil {
                q = append(q, node.Left)
            }
            if node.Right != nil {
                q = append(q, node.Right)
            }
        }

        if i&1 == 1 {
            reverse(nums)
        }
        ans = append(ans, nums)
    }
    return ans
}

C++