文档章节

剑指Offer(Java版):从上往下打印二叉树

一贱书生
 一贱书生
发布于 2016/07/22 22:16
字数 660
阅读 46
收藏 0

题目:从上往下打印二叉树的每个结点,同一层的结点按照从左到右的顺序打印。例如输入下图的二叉树,则一次打印出8,6,10,5,7,9,11.

这道题实质上考察的就是树的遍历算法,只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法,可能已下载也想不清楚遍历的过程。

因为按层打印的顺序决定应该先打印的根节点,所以我们从树的根节点开 始分析。为了接下来能够打印8的结点的两个子节点,我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器中,现在容器内就有两个结点了。按照 从左到右打印的要求,我们先取出值为6的结点。打印出6后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有三个结点,值分别为 10,5,7.接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5,7,的结点先放入容器,此时又比这两个结点先取出,这就是我们 通常说的先入先出,因此不难看出这个容器应该是一个队列。由于值为5,7,9,11的结点都没有子节点,因此只要依次打印即可。

通过分析具体例子,我们可以找到从上到下打印二叉树的规律:每一次打印一个结点的时候,如果该结点有子节点,把该结点的子节点放到一个队列的尾。接下来到队列的头部取出最早进入队列的结点,重复前面打印操作,直到队列中所有的结点都被打印出为止。

Java代码实现:

 

package cglib;

import java.util.LinkedList;
import java.util.Queue;

class BinaryTreeNode{
    
    int value;
    BinaryTreeNode leftNode;
    BinaryTreeNode rightNode;
    
}


public class DeleteNode {
    public static void main(String args[])
    { BinaryTreeNode root1=new BinaryTreeNode();
    BinaryTreeNode node1=new BinaryTreeNode();
    BinaryTreeNode node2=new BinaryTreeNode();
    BinaryTreeNode node3=new BinaryTreeNode();
    BinaryTreeNode node4=new BinaryTreeNode();
    BinaryTreeNode node5=new BinaryTreeNode();
    BinaryTreeNode node6=new BinaryTreeNode();
    root1.leftNode=node1;
    root1.rightNode=node2;
    node1.leftNode=node3;
    node1.rightNode=node4;
    node4.leftNode=node5;
    node4.rightNode=node6;
    root1.value=8;
    node1.value=8;
    node2.value=7;
    node3.value=9;
    node4.value=2;
    node5.value=4;
    node6.value=7;
    DeleteNode test=new DeleteNode();
    test.printFromTopToBottom(root1);
    }
    
    public void printFromTopToBottom(BinaryTreeNode root){
        if(root==null)
        return;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
        BinaryTreeNode node=queue.poll();
        System.out.print(node.value);
        if(node.leftNode!=null){
        queue.add(node.leftNode);
        }
        if(node.rightNode!=null){
        queue.add(node.rightNode);
        }
        }
        }
}

 

输出:

8879247

© 著作权归作者所有

一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
0
0
面试:用 Java 逆序打印链表

面试:用 Java 逆序打印链表 昨天的 Java 实现单例模式 中,我们的双重检验锁机制因为指令重排序问题而引入了 关键字,不少朋友问我,到底为啥要加 这个关键字呀,而它,到底又有什么神奇的作...

nanchen2251
2018/07/03
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 1. 栈的 java 实现 2. 队列的 java 实现 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 Le...

繁著
2018/09/04
0
0
给广大码农分享福利:一个业界良心的github仓库,中文计算机资料

我今天查资料时无意发现的,https://github.com/CyC2018/CS-Notes 这个仓库包含了下列几个维度的计算机学习资料: 深受国内程序员喜爱,已经有超过3万多star了。 1. 算法 (1) 剑指 Offer 题解...

JerryWangSAP
2018/10/12
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在工作中快速成长?致工程师的10个简单技巧

阿里妹导读:阿里有句非常经典的土话,“今天的最好表现,是明天的最低要求。”如何挖掘潜能、发现更好的自己?今天,阿里巴巴高级无线开发专家江建明将认知升级的方法总结出来,帮助你获得快...

阿里云云栖社区
29分钟前
1
0
PHP和Redis实现在高并发下的抢购及秒杀功能

抢购、秒杀是平常很常见的场景,面试的时候面试官也经常会问到,比如问你淘宝中的抢购秒杀是怎么实现的等等。 抢购、秒杀实现很简单,但是有些问题需要解决,主要针对两个问题: 一、高并发对...

xiaogg
31分钟前
1
0
从数据上看:谁才是漫威的绝对C位

复联4上映了!这次比美国还早了两天。当然,我还没看,不会给你们剧透,当然也不想不剧透。 这一部不仅是灭霸这一线剧情的结局,也被认为漫威第三阶段的收官之作。据说此部之后,不少影迷熟知...

crossin
44分钟前
4
0
Spring Cloud底层原理

毫无疑问,Spring Cloud 是目前微服务架构领域的翘楚,无数的书籍博客都在讲解这个技术。 不过大多数讲解还停留在对 Spring Cloud 功能使用的层面,其底层的很多原理,很多人可能并不知晓。 ...

月下狼
54分钟前
8
0
Linux重启Tomcat

在测试过程中,要构建测试环境,还经常要重启Tomcat排查问题,重启Tomcat的步骤: 1、首先查看Tomcat是否有启动或重复启动? 输入命令ps -aux|grep java按回车键,可见下图,是有一个Tomcat启...

测试龙管家
55分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部