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

一、题目

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

二、示例

2.1> 示例1

提示：

• 节点总数 <= 1000

三、解题思路

• 本题是算法《剑指 Offer 32 - II. 从上到下打印二叉树 II》题的变形，在原有层序遍历的基础上，根据奇数层按照由左到右进行输出，而根据偶数层则按照从右向左进行输出；
• 那么层序遍历我们之前的题解中提到过，通过采用双向队列Deque<TreeNode> deque以及配合当前层级的节点数num就可以实现按层遍历操作，那么本题的难点就在于如何根据奇数/偶数层数来转换遍历节点。
• 为了实现遍历结果的反转，我们可以再创建一个变量LinkedList<Integer> item，由于LinkedList提供了从头部开始链接的addFirst(...)方法和从尾部开始链接的addLast(...)方法，所以我们只需执行如下操作：

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

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

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

四、代码实现

publicclassSolution {
publicList<List<Integer>>levelOrder(TreeNoderoot) {
List<List<Integer>>result=newArrayList();
if (root==null) returnresult;
Deque<TreeNode>deque=newArrayDeque();
deque.addLast(root);
intnum;
booleanreverse=false;
while(!deque.isEmpty()) {
num=deque.size();
LinkedList<Integer>item=newLinkedList<>();
for (inti=0; i<num; i++) {
TreeNodenode=deque.removeFirst();
if (reverse) item.addFirst(node.val);
elseitem.addLast(node.val);
if (node.left!=null) deque.addLast(node.left);
if (node.right!=null) deque.addLast(node.right);
            }
result.add(item);
reverse=!reverse;
        }
returnresult;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」