二叉树锯齿形层次遍历算法详解及Java实现

二叉树的锯齿形层次遍历是一种特殊的二叉树层序遍历方式，它不同于常规的先序、中序或后序遍历，而是根据节点所在层级的奇偶性改变输出顺序。在锯齿形层次遍历中，如果当前层是偶数层，则按照从左到右的顺序输出节点值；如果是奇数层，则按照从右到左的顺序输出。 实现这个算法的关键在于利用广度优先搜索（BFS）的方法，但在此基础上进行一些调整。具体步骤如下： 1. 使用队列（通常为`LinkedList`）存储当前层的节点，初始化时将根节点加入队列。 2. 在遍历过程中，计算队列的当前长度，表示当前层的节点数量。 3. 每次从队列中取出一定数量的节点进行扩展，并更新下一层节点。为了保持锯齿形状，这里使用双端队列（`Deque`），它允许在队列两端添加或删除元素。在添加节点时，会根据`isOrderLeft`标志来决定是添加到队列尾部（左出）还是头部（右出）： - 如果`isOrderLeft`为`true`，则按照从左至右的顺序添加节点。 - 如果`isOrderLeft`为`false`，则按照从右至左的顺序添加节点。 4. 遍历完一层节点后，根据层数奇偶性切换`isOrderLeft`的状态，然后继续下一层的遍历，直到队列为空。 Java实现时，首先检查根节点是否为空，然后创建`TreeNode`队列，设置初始的`isOrderLeft`为`true`。在主循环中，不断处理队列，维护结果列表`ans`，直到队列为空。这样就得到了锯齿形层次遍历的结果。 例如，对于输入`root=[3,9,20,null,null,15,7]`，输出将是`[[3],[20,9],[15,7]]`，这表明第一层输出3，第二层先输出20，再输出9，第三层先输出15，再输出7。这种方法不仅考虑了节点的层次，还体现了题目中要求的锯齿形输出模式。