[剑指offer] 按之字形顺序打印二叉树
本文首发于我的个人博客:尾尾部落
题目描述
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
解题思路
设两个栈,s2存放奇数层,s1存放偶数层
遍历s2节点的同时按照左子树、右子树的顺序加入s1,
遍历s1节点的同时按照右子树、左子树的顺序加入s2
参考代码
import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); int flag = 1; if(pRoot == null) return res; s2.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); while(!s1.isEmpty() || !s2.isEmpty()){ if(flag % 2 != 0){ while(!s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val); if(node.left != null){ s1.push(node.left); } if(node.right != null){ s1.push(node.right); } } } if(flag % 2 == 0){ while(!s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val); if(node.right != null){ s2.push(node.right); } if(node.left != null){ s2.push(node.left); } } } res.add(new ArrayList<Integer>(temp)); temp.clear(); flag ++; } return res; } }
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
深入 Java 核心
类加载 类加载负责加载编译后的class文件(字节码文件)到JVM当中。 在JRE中,类加载器主要分为以下几种: 引导类加载器(Bootstrap) 它本身使用C/C++语言实现的,负责加载Java的核心类库,在jre\lib目录中,当中包括如rt.jar,这些都是Java自带的核心类库,必须由它来完成加载。 拓展/扩展类加载器(Extension) 这个加载器就是由Java语言实现,负责加载jre\lib\ext目录下的类库,这个目录下的类库都是一些扩展类。 应用程序/系统类加载器(Application) 这个类加载器同样使用Java语言实现,它主要负责加载classpath下面的所有类库,通常我们编写的Java类都是由这个类加载器完成加载。 三个类加载器的初始化过程:当程序运行时,首先会初始化引导类加载器,它就负责创建和初始化扩展类加载器,当扩展类加载器完成初始化之后,又负责创建和初始化系统类加载器。 这些类加载器协同起来完成整个类加载的过程,因此这些类加载器的加载模式是基于“双亲委托模型”。 举例说明 当我们编写一个Java类时,首先负责加载这个类的加载器是系统类加载器,但是它...
- 下一篇
Python字符串基础操作
找到我就是缘分,为技术一起努力! 格式符 # price_width = 10 item_width = width - price_width header_format = '%-*s%*s' format = '%-*s%*.2f' print '=' * width print header_format % (item_width, 'Item', price_width, 'Price') print '-' * width print format % (item_width,'Apples',price_width,0.4) print format %(item_width,'Pears', price_width,0.5) print format %(item_width,'Cantaloupes',price_width,1.92) find(str,start,end):从start开始end结束寻找与str相匹配的字符,找到返回匹配项index,找不到返回-1 a='With a moo-moo here. and a moo-moo there'.find...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
-
Docker使用Oracle官方镜像安装(12C,18C,19C)
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8编译安装MySQL8.0.19
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- MySQL8.0.19开启GTID主从同步CentOS8
- CentOS7,8上快速安装Gitea,搭建Git服务器
- Jdk安装(Linux,MacOS,Windows),包含三大操作系统的最全安装
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果
推荐阅读
最新文章
- SpringBoot2全家桶,快速入门学习开发网站教程
- SpringBoot2更换Tomcat为Jetty,小型站点的福音
- Springboot2将连接池hikari替换为druid,体验最强大的数据库连接池
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- MySQL8.0.19开启GTID主从同步CentOS8
- Docker快速安装Oracle11G,搭建oracle11g学习环境
- SpringBoot2整合Redis,开启缓存,提高访问速度
- Windows10,CentOS7,CentOS8安装Nodejs环境
- CentOS7编译安装Cmake3.16.3,解决mysql等软件编译问题
- SpringBoot2编写第一个Controller,响应你的http请求并返回结果