专栏首页五分钟学算法今天,带你学会二叉树的打印

今天,带你学会二叉树的打印

你好,我是吴师兄,今天继续上算法干货。

读完本文,和二叉树打印相关的题目你都可以拿下,由于本文图片很多,建议在 WIFI 环境下阅读

首先是第一道,从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印,比如给定二叉树 [3,9,20,null,null,15,7]

返回 [3,9,20,15,7]

解题思路很简单,借助一个队列。

每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直至队列中所有的结点都被打印出来为止。

整个过程如下图片所示:

代码如下:

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public int[] levelOrder(TreeNode root) {
        // 根节点为空的情况返回空数组
        if (root == null) return new int[0];
        // 生成一个队列,用来保存节点
        Queue<TreeNode> queue = new LinkedList<>();

        // 生成一个 list,用来保存输出的节点
        List<Integer> list = new ArrayList<>();
        // 首先让根节点入队
        queue.add(root);

        // 遍历队列,直到队列为空
        while (!queue.isEmpty()) {
            // 获取队列的头部元素
            TreeNode node = queue.poll();
            // 把结点值存放到 list 中
            list.add(node.val);
            // 判断该节点是否有左右子节点

            // 如果左子节点有值,则把左子节点加入到队列中
            if (node.left != null){
                queue.add(node.left); 
            }
            // 如果右子节点有值,则把右子节点加入到队列中 
            if (node.right != null){
              queue.add(node.right);
            }          

    }
        // 根据题目要求,把 list 转化为数组
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        // 返回 res
        return res;
    }
}

第二道题目则是在第一道的基础上添加了一个要求同一层的节点按照从左到右的顺序打印,意思就是输出变成了这个样子:

[
    [3],
    [9,20],
    [15,7]
]

所以,代码整体和第一道是类似的,只不过为了将同一层的元素放到一个数组汇总,需要记录每一层的元素个数,这里可以直接通过队列的长度来获取

来看设计过程:

代码如下:

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 设置 res 用来保存输出结果
        List<List<Integer>> res = new LinkedList<>();
        // 边界情况处理
        if(root == null) return res;

        // 设置一个队列,用来存储二叉树中的元素
        Queue<TreeNode> queue = new LinkedList<>();
        // 队列添加二叉树的根节点
        queue.add(root);

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while(!queue.isEmpty()){  
            // 用来记录 queue 的长度,即每层节点的个数
            int size = queue.size();  

            // 用来保存每一层节点,保存成功后添加到 res 中
            List<Integer> temp =  new ArrayList<>(); 

            // 使用 for 循环,将 queue 中的元素添加的 temp 中
            for(int i = 0 ; i < size ;  i++ ){     
                // 从 queue 中取出一个节点         
                TreeNode node = queue.poll();  
                // 把节点存放到 list 中
                temp.add(node.val);  //将节点值加入list

                // 判断当前节点的左子节点是否有值,如果有,则添加到 queue 中
                if(node.left != null)
                    queue.add(node.left);

                // 判断当前节点的右子节点是否有值,如果有,则添加到 queue 中    
                if(node.right != null)
                    queue.add(node.right);
            }

            // 把存放了每一层元素的数组 temp 添加到 res 中
            res.add(temp);
        }

        // 返回 res
        return res;       
    }   
}

最后一道也是在第二道的基础上变形:请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。

输出变成了:

[
    [3],
    [20,9],
    [15,7]
]

翻译过来的意思就是,奇数层顺序打印,偶数层逆序打印,实现思路上可以通过设置一个标志位 isOddNumber 用来判断当前的层数是否为奇数层:

  • 如果是奇数层,那么按顺序把 queue 中的元素添加到双端队列 temp 的尾部
  • 如果是偶数层,那么按顺序把 queue 中的元素添加到双端队列 temp 的头部

解题过程如下:

代码如下:

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {

        // 设置 res 用来保存输出结果
        List<List<Integer>> res = new LinkedList<>();

        // 边界情况处理
        if(root == null) return res;

        //设置一个队列,用来存储二叉树中的元素
        Queue<TreeNode> queue = new LinkedList<>();

        // 队列添加二叉树的根节点
        queue.add(root);

        // 用来判断当前的层数是否为奇数层,初始化在第 0 层,为偶数层
        boolean isOddNumber = false;

        // 遍历队列,直到队列为空,说明访问了二叉树中所有的节点
        while(!queue.isEmpty()) {

            // 用来记录 queue 的长度,即每层节点的个数
            int size = queue.size();  

            // 奇偶层总是交替出现的
            // 通过取反操作,判断当前的层数是否为奇偶层
            // 由于 isOddNumber 初始化为 false,所以第一次进来这个 while 循环取反后为 true,符合第一层是奇数层的定义
            isOddNumber = !isOddNumber;

            // 生成一个双端队列 temp,用来保存每一层节点,保存成功后添加到 res 中
            LinkedList<Integer> temp = new LinkedList<>();

            // 使用 for 循环,将 queue 中的元素按照给定的规则添加的 temp 中
            for(int i = 0 ; i < size; i++) {
                // 从 queue 中取出一个节点    
                TreeNode node = queue.poll();
                // 如果是奇数层,那么按顺序添加到双端队列的尾部
                if(isOddNumber) {
                    temp.addLast(node.val); 
                }else {
                    // 如果是偶数层,那么按顺序添加到双端队列的头部
                    temp.addFirst(node.val);
                }

                // 判断当前节点的左子节点是否有值,如果有,则添加到 queue 中
                if(node.left != null) queue.add(node.left);

                // 判断当前节点的右子节点是否有值,如果有,则添加到 queue 中    
                if(node.right != null) queue.add(node.right);
            }
            // 把存放了每一层元素的数组 temp 添加到 res 中
            res.add(temp);
        }

        // 返回 res
        return res;
    }
}

今天的内容就是这些,总的来说,关于二叉树打印的这三道算法题在整体的思考方向上都是一致的,都需要借助辅助结构队列用来临时存储二叉树中的节点元素,然后再按照题目的要求进行输出。

遇到二叉树的算法题,如果思路上遇到瓶颈,亲自手绘一下过程往往可以帮到你。

接下来的一段时间吴师兄在持续更新图解算法、图解数据结构系列的间隙,也会给大家带来诸如二叉树的序列化平衡二叉树等难度较高的题目,希望能帮助你彻底攻克二叉树,记得星标五分钟学算法,这样能第一时间收到推送,觉得有收获不妨点赞,我们下期内容再见。

本文分享自微信公众号 - 五分钟学算法(CXYxiaowu),作者:程序员吴师兄

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-07-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Day68:剑指Offer总结

      本人花了两个月时间刷完了牛客网带上的剑指Offer,一共67题。本人是从4月21日开始刷题,每天一题,截止到7月6日已经全部刷完。这67题均是考察的数据结构...

    一计之长
  • 程序员,你心里就没点‘树’吗?

    看官,不要生气,我没有骂你也没有鄙视你的意思,今天就是想单纯的给大伙分享一下树的相关知识,但是我还是想说作为一名程序员,自己心里有没有点树?你会没点数吗?言归正...

    田维常
  • 二叉树小结及习题—展开为链表

    通过三种遍历情况,我们可以发现的共通点是:都是先左节点,后右节点,只是中间节点的位置不同。 所以综合一下,可以得出一种通用的二叉树遍历方法,是一种递归算法:

    码上积木
  • 二叉树遍历就是这么简单(必杀)

    小编带大家学习数据结构中的二叉树,我们这里的实现主要是用 C 语言去实现的,当然也有 C++的语法,用基础的语言有助于我们更好理解数据结构。

    机智的程序员小熊
  • 树+8道前端算法面试高频题解

    A 是 根节点。C、D、F、G 是 叶子节点。A 是 B 和 E 的 父节点。B 和 E 是 A 的 子节点。B、E 之间是 兄弟节点。

    童欧巴
  • Python 实现二叉树的增、删、查

    学过数据结构的同学一定对树这种数据结构非常熟悉了,树是一种非常高效的非线性存储结构,学好树对理解一些复杂的算法非常有帮助。树有以下内容需要掌握:

    somenzz
  • 800道面试题和43道JAVA算法/数据结构面试题

    输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字...

    搜云库技术团队
  • 两分钟弄懂对称二叉树

    大家好呀,我是吴师兄,今天照例来更新一道 LeetCode 算法题,根据以往数据来看,这类文章的打开率普遍不高,一般在三四千左右,远远低于水文或者热点文一两万的...

    五分钟学算法
  • 树和二叉树

    树的概念其实非常地广泛,也非常地常见,大家见到这个词千万不要惊慌,因为真的每天你都能见到树结构在我们生活中的应用。比如说公司的组织结构:

    硬核项目经理
  • 从入门到修仙的算法之路

    最近开展了每天一道leetcode/每天一道剑指offer的刷题活动,总有很多人问我,该如何刷题/零基础如何开始刷题,这里和大家分享一下我的经验。

    乔戈里
  • 二叉树的基础---四种遍历方式的 Java 实现

    大家好,我是多选参数的程序锅,一个正在“研究”操作系统、学数据结构和算法以及 Java 的硬核菜鸡。本篇将带来的是二叉树的相关知识,知识提纲如图所示。

    syy
  • 「种树专业户」“树”业有专攻

    食堂老板(童欧巴):就算我们作为互联网浪潮中的叶子结点,也需要有蚍蜉撼树的精神,就算蚍蜉撼树是自不量力。因为就算终其一生只是个普通人,但你总不能为了成为一个普通...

    童欧巴
  • 聊聊二叉树的遍历(递归和非递归)

    二叉树也是常用的数据结构,通过使用二叉树可以快速的对数据进行排序或者查找,在常用的堆排序算法中,堆的底层实质就是一个模拟的完全二叉树!等等,什么是完全二叉树?二...

    算法工程师之路
  • Dimple在左耳听风ARTS打卡(十七)

    所谓ARTS:每周至少做一个LeetCode的算法题;阅读并点评至少一篇英文技术文章;学习至少一个技术技巧;分享一篇有观点和思考的技术文章。(也就是Algori...

    程序员小跃
  • 每天一道剑指offer-从上往下打印二叉树

    今天的题目 每天的题目见github(看最新的日期): https://github.com/gzc426 具体的题目可以去牛客网对应专题去找。

    乔戈里
  • 谈树,2020 希望有所建「树」

    数据结构是 10 年前大学里学的一门课程,也是我北漂唯一携带的一本书。幸运的是,书还没有被孩子给撕碎。

    一猿小讲
  • 数据结构——堆

    对于接触编程的人员来说,堆这个词经常会听到,经常和一群名次混合堆区,栈区,静态区等等,面试的时候可能经常也会遇到一个算法,堆排,今天小编主要和大家一起来看看堆这...

    机智的程序员小熊
  • 之字形遍历二叉树——你为何这么浪

    说到二叉树遍历,脑海中立刻想到的就是深度优先遍历和广度优先遍历,这两种方式相信大家都驾轻就熟了,就不再过多累赘。

    蜻蜓队长
  • 【刷题】2020最新剑指Offer汇总

    新手村 关卡1-1 洛谷的第一个任务 P1000 超级玛丽游戏:点击这里 P1001 A+B Problem:点击这里 P1421 小玉买文具:点击这里...

    瑞新

扫码关注云+社区

领取腾讯云代金券