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

图解LeetCode——剑指 Offer 32 - III. 从上到下打印二叉树 III

news 2025/6/28 10:12:36

一、题目

请实现一个函数按照之字形顺序打印二叉树，即：第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

二、示例

2.1> 示例1

提示：

节点总数 <= 1000

三、解题思路

本题是算法《剑指 Offer 32 - II. 从上到下打印二叉树 II》题的变形，在原有层序遍历的基础上，根据奇数层按照由左到右进行输出，而根据偶数层则按照从右向左进行输出；

那么层序遍历我们之前的题解中提到过，通过采用双向队列Deque deque以及配合当前层级的节点数num就可以实现按层遍历操作，那么本题的难点就在于如何根据奇数/偶数层数来转换遍历节点。

为了实现遍历结果的反转，我们可以再创建一个变量LinkedList item，由于LinkedList提供了从头部开始链接的addFirst(...)方法和从尾部开始链接的addLast(...)方法，所以我们只需执行如下操作：

【奇数层】调用addLast(...)方法进行item的子结果拼装；
【偶数层】调用addFirst(...)方法进行item的子结果拼装；

那么最终将每层的item组合到最终结果List<List> result即可。根据上面介绍的解题思路，我们以二叉树结构[1,2,3,4,5,6,7]为例，具体看一下针对这道题的处理逻辑。请见下图所示：

四、代码实现

public class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> result = new ArrayList();if (root == null) return result;Deque<TreeNode> deque = new ArrayDeque();deque.addLast(root);int num;boolean reverse = false;while(!deque.isEmpty()) {num = deque.size();LinkedList<Integer> item = new LinkedList<>();for (int i = 0; i < num; i++) {TreeNode node = deque.removeFirst();if (reverse) item.addFirst(node.val);else item.addLast(node.val);if (node.left != null) deque.addLast(node.left);if (node.right != null) deque.addLast(node.right);}result.add(item);reverse = !reverse;}return result;}
}