当前位置：首页 > news >正文

算法的学习笔记---按之字形顺序打印二叉树

news 2025/11/26 14:05:37

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

🏠个人主页：尘觉主页

文章目录

🥰按之字形顺序打印二叉树
- 😊问题描述
- - 举例说明
- 🤔解题思路
- 😁代码实现
- - 代码解析
- 😄总结

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

😊问题描述

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

举例说明

假设我们有以下二叉树：

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

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

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

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

🤔解题思路

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

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

😁代码实现

以下是该算法的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;}
}