刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你二叉树的根节点 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

思路

其实第一眼看到这个，大家应该都明白，这个就是一个层序遍历的变种，类似的问题，如果附加的变种条件不是很明确的话，建议可以先把层序遍历基础方法或者伪代码写出来，可以帮助思考。

至于本问题的变种，其实就是每层切换一下遍历子节点的方向。我的思路是，那就每一层都反着来，然后再加上一个自旋开关，来配合切换先走左子节点还是先走右子节点即可。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	levelNodes := []*TreeNode{root}
	directLeft := true
	res := make([][]int, 0)
	for len(levelNodes) > 0 {
		levelNums := make([]int, 0)
		tempNodes := make([]*TreeNode, 0, len(levelNodes)*2)
		for i := len(levelNodes) - 1; i >= 0; i-- {
			levelNums = append(levelNums, levelNodes[i].Val)
			if directLeft {
				if levelNodes[i].Left != nil {
					tempNodes = append(tempNodes, levelNodes[i].Left)
				}
				if levelNodes[i].Right != nil {
					tempNodes = append(tempNodes, levelNodes[i].Right)
				}
			} else {
				if levelNodes[i].Right != nil {
					tempNodes = append(tempNodes, levelNodes[i].Right)
				}
				if levelNodes[i].Left != nil {
					tempNodes = append(tempNodes, levelNodes[i].Left)
				}
			}
		}
		res = append(res, levelNums)
		levelNodes = tempNodes
		directLeft = !directLeft
	}
	return res
}

看到这里了，点个赞点个在看呗！~ 多谢大家的支持！~