剑指Offer（六十）-- 将二叉树打印成多行

秦怀杂货店

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

2010

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

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

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

题目描述

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

示例1

输入

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

返回值

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

思路以及解答

和前面的题差不多，甚至更加简单：

借助双向链表，先将根节点添加进去：
获取list里面剩下的元素的个数，挨个取出就是一层，取出的时候，添加到当前层的list结果集中，然后判断每一个取出来的节点的左右节点是不是为空，不为空则加入链表。（按照层次遍历的时候需要按照size来循环）
每一层处理完之后，将list加入结果集中，继续判断list是不是为空，执行第二步循环。

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

public class Solution60 {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        LinkedList<TreeNode> nodes = new LinkedList<>();
        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();
                    integers.add(node.val);
                    if (node.left != null) {
                        nodes.add(node.left);
                    }
                    if (node.right != null) {
                        nodes.add(node.right);
                    }
                }
                if (!integers.isEmpty()) {
                    results.add(integers);
                }
            }
        }
        return results;
    }
}

借助了队列，空间复杂度为O(n)，时间复杂度为O(n)。

【作者简介】：

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

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

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

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

编程算法