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

题目

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

例如

给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

算法

广度优先遍历

题目要求按层遍历树，所以我们使用广度优先遍历。类似102 - 二叉树的层序遍历 (opens new window)，不同的是要求按照奇偶层交替遍历方向，所以我们使用变量fromLeft来控制方向

我们声明一个数组res来保存结果

如果我们上一层是从左向右遍历的，那么下一层我们就会从右向左遍历，所以上一层后遍历的节点的子节点在下一层会被先遍历到，是后进先出，所以我们使用栈stack来保存当前这一层需要遍历的节点

我们这里使用双循环来遍历整个树，外层循环控制层，内层循环控制每一层的节点：

• 每一层开始遍历时，我们需要在res的末尾新建一个空数组来保存当前层的节点值，并创建一个nextRow的数组用来保存下一层将要遍历的节点
• stack中保存的是当前层要遍历的节点，我们按照方向变量fromLeft将存在的子节点推入，如果是从左向右遍历层，我们对于每一个节点就先向nextRow中推入左子节点；如果是从右向左遍历层，我们对于这一层每一个节点就先将右子节点推入nextRow
• 当前层遍历结束后，我们对方向变量fromLeft取反，然后将nextRow赋值给stack作为下一层的遍历的节点，如果stack为空说明遍历树结束，返回res

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
export const zigzagLevelOrder = function (root) {
	if (!root) return [];
	const stack = [root];
	const res = [];
	let fromLeft = true;
	while (stack.length) {
		const nextRow = [];
		res.push([]);
		while (stack.length) {
			const curNode = stack.pop();
			res[res.length - 1].push(curNode.val);
			if (fromLeft) {
				if (curNode.left) nextRow.push(curNode.left);
				if (curNode.right) nextRow.push(curNode.right);
			} else {
				if (curNode.right) nextRow.push(curNode.right);
				if (curNode.left) nextRow.push(curNode.left);
			}
		}
		fromLeft = !fromLeft;
		stack.push(...nextRow);
	}
	return res;
};