剑指Offer（五十九）-- 按之字形顺序打印二叉树

秦怀杂货店

发布于 2022-02-15 14:06:46

3560

文章被收录于专栏：技术杂货店技术杂货店

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

示例1

输入

{8,6,10,5,7,9,11}

返回值

[[8],[10,6],[5,7,9,11]]

思路以及解答

借助双向链表，初始化一个添加方向boolean值，先将根节点添加进去：
获取list里面剩下的元素的个数，挨个取出就是一层，取出的时候，如果reverse为true，则往链表的第0个索引位置添加，否则直接在后面添加，然后判断每一个取出来的节点的左右节点是不是为空，不为空则加入链表。
每一层处理完之后，将list加入结果集中，然后翻转reverse的值，继续判断list是不是为空，执行第二步循环。

代码如下：


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Solution{
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        LinkedList<TreeNode> nodes = new LinkedList<>();
        ArrayList <ArrayList<Integer>>results = new ArrayList();
        boolean reverse = true;
        if(pRoot!=null){
            nodes.add(pRoot);
            while(!nodes.isEmpty()) {
                ArrayList<Integer> integers = new ArrayList();
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = nodes.poll();
                    if(reverse){
                        integers.add(node.val);
                    }else{
                        integers.add(0,node.val);
                    }
                    if (node.left!=null){
                        nodes.offer(node.left);
                    }
                    if(node.right!=null){
                        nodes.offer(node.right);
                    }
                }
                if(integers.size()!=0){
                    results.add(integers);
                }
                reverse=!reverse;
            }
        }
        return results;
    }
}

空间复杂度由于借助了额外的list，为O(n)，时间复杂度上，由于每个节点进入队列又出来，为O(2n)，也是O(n)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法