😀前言
在算法的学习中，二叉树是一种非常基础但又十分重要的数据结构。今天，我们将讨论一种特殊的二叉树遍历方法：之字形顺序打印。这个方法要求我们以“之”字形的顺序遍历并打印二叉树的节点值，也就是第一行从左到右，第二行从右到左，第三行再从左到右，以此类推。这种遍历方式不仅能加深我们对二叉树结构的理解，还能为某些特殊的实际应用提供算法支持。

🥰按之字形顺序打印二叉树

😊问题描述

我们需要实现一个函数来完成这一任务。给定一个二叉树，我们要按之字形顺序遍历二叉树，并将每一层的节点值按要求的顺序保存下来，最后返回结果。

举例说明

假设我们有以下二叉树：

        1
       / \
      2   3
     / \ / \
    4  5 6  7

按之字形顺序打印的结果应该是：

[
 [1],
 [3, 2],
 [4, 5, 6, 7]
]

第一行按照从左到右的顺序打印：1；第二行按照从右到左的顺序打印：3, 2；第三行再按照从左到右的顺序打印：4, 5, 6, 7。

🤔解题思路

为了实现这个功能，我们可以使用广度优先搜索（BFS）的方法，即层序遍历二叉树。具体来说，我们可以利用队列来保存当前层的节点，同时通过一个布尔变量来标记当前层的遍历方向。以下是详细的步骤：

1. 初始化：创建一个队列用于层序遍历，并将根节点加入队列。创建一个结果列表用于保存每层的节点值。
2. 遍历每一层：
   • 对于当前层的每一个节点，从队列中取出并将其子节点（如果存在）加入队列。
   • 将当前节点的值保存到一个列表中。
   • 如果当前层需要反向打印（从右到左），则反转列表中的值。
3. 切换遍历方向：在遍历完当前层之后，切换下一个层次的遍历方向。
4. 返回结果：将每一层的节点值按顺序加入结果列表中并返回。

😁代码实现

以下是该算法的Java实现代码：

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        boolean reverse = false; // 标记是否需要反向
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int cnt = queue.size();
            while (cnt-- > 0) {
                TreeNode node = queue.poll();
                if (node == null)
                    continue;
                list.add(node.val);
                queue.add(node.left);
                queue.add(node.right);
            }
            if (reverse) // 如果当前层需要反向
                Collections.reverse(list);
            reverse = !reverse; // 切换遍历方向
            if (list.size() != 0)
                ret.add(list);
        }
        return ret;
    }
}

代码解析

1. 队列的使用：队列是广度优先搜索的经典工具，利用它，我们可以逐层遍历二叉树。
2. 反向操作：每遍历一层后，我们会检查当前是否需要反向打印，如果需要，则使用Collections.reverse()方法反转当前层的列表。
3. 布尔变量切换方向：通过布尔变量reverse的切换，我们能轻松地控制下一层的遍历方向。

😄总结

之字形顺序打印二叉树是一种层序遍历的变种，它要求我们在遍历每层节点时，按指定的方向打印。这种问题不仅考察我们对二叉树遍历的掌握，还需要我们灵活运用数据结构来管理遍历的顺序。通过上述代码，我们可以高效地实现这一功能，并在复杂的树结构中应用。