文档章节

【九度OJ1523】从上往下打印二叉树

aqia358
 aqia358
发布于 2013/12/24 09:35
字数 612
阅读 76
收藏 0
题目描述:

从上往下打印出二叉树的每个节点,同层节点从左至右打印。

输入:

输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行一个整数n(1<=n<=1000, :n代表将要输入的二叉树元素的个数(节点从1开始编号)。接下来一行有n个数字,代表第i个二叉树节点的元素的值。接下来有n行,每行有一个字母Ci。
Ci=’d’表示第i个节点有两子孩子,紧接着是左孩子编号和右孩子编号。
Ci=’l’表示第i个节点有一个左孩子,紧接着是左孩子的编号。
Ci=’r’表示第i个节点有一个右孩子,紧接着是右孩子的编号。
Ci=’z’表示第i个节点没有子孩子。

输出:

对应每个测试案例,
按照从上之下,从左至右打印出二叉树节点的值。

样例输入:
7
8 6 5 7 10 9 11
d 2 5
d 3 4
z
z
d 6 7
z
z
样例输出:
8 6 10 5 7 9 11
解:先将根保存到一个list中,打印这个list,并将其左右孩子放到另一个list中,递归打印这个list
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.List;

/**
 * 21时47分07秒
 * @author aqia358
 *
 */
public class Main {
	public static int count ;

	static class Node{
		public int data;
		public Node left = null;
		public Node right = null;
		
		public Node(int data){
			this.data = data;
		}
		
	}
	public static Node find(int data,Node node){
		if(node != null){
			if(node.data == data)
				return node;
			else{
				Node nodel = find(data, node.left);
				Node noder = find(data, node.right);
				if(nodel != null)
					return nodel;
				else if(noder != null)
					return noder;
				else 
					return null;
			}
		}else{
			return null;
		}
	}
	public static void doPrint(Node node){
		List<Node> list = new ArrayList<Node>();
		list.add(node);
		print(list);
		System.out.println();
	}
	public static void print(List<Node> list){
		if(list != null && list.size() > 0){
			List<Node> son = new ArrayList<Node>();
			for(Node node:list){
				if(node != null){
					System.out.print(node.data);
					if(count != 1){
						count--;
						System.out.print(" ");
					}
					son.add(node.left);
					son.add(node.right);
				}
			}
			print(son);
		}
	}
	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != StreamTokenizer.TT_EOF){
			int n = (int)st.nval;
			int[] a = new int[n];
			for(int i = 0; i < n; i++){
				st.nextToken();
				a[i] = (int) st.nval;
			}
			Node root = new Node(a[0]);
			for(int j = 1;j <= n; j++){
				st.nextToken();
				String op = st.sval;
				Node node = Main.find(a[j - 1], root);
				if(op.equals("d")){
					st.nextToken();
					int left = (int)st.nval;
					st.nextToken();
					int right = (int)st.nval;
					node.left = new Node(a[left - 1]);
					node.right = new Node(a[right - 1]);
				}else if(op.equals("l")){
					st.nextToken();
					int left = (int)st.nval;
					node.left = new Node(a[left - 1]);
				}else if(op.equals("r")){
					st.nextToken();
					int right = (int)st.nval;
					node.right = new Node(a[right - 1]);
				}
			}
			Main.count = n;
			Main.doPrint(root);
		}
	}

}






© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
私信 提问
剑指offer 23. 从上往下打印二叉树

原题 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 Reference Answer 解题思路: 思路:用一个临时数组存储需要打印的节点,如打印8时,将6和10存入临时数组 Note 这道题解题方式...

dby_freedom
11/01
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
从上往下打印二叉树

从上往下打印出二叉树的每个节点,同层节点从左至右打印。 思路:层次遍历。也是bfs的应用。利用队列实现

战地春梦
2016/05/09
33
0
从上往下打印二叉树

题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左到右的顺序打印。 解题思路:每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到...

许大树
2017/10/23
0
0
[剑指offer] 从上往下打印二叉树

题目描述 从上往下打印出二叉树的每个节点,同层节点从左至右打印。 解题思路 就是二叉树的层序遍历。借助一个队列就可以实现。 使用两个队列一个存放节点,一个存放值。先将根节点加入到队列...

繁著
06/30
0
0

没有更多内容

加载失败,请刷新页面

加载更多

《大漠烟尘》读书笔记及读后感文章3700字

《大漠烟尘》读书笔记及读后感文章3700字: 在这个浮躁的社会里,你有多久没有好好读完一本书了? 我们总觉得自己和别人不一样,所以当看到别人身上的问题时,很少有“反求诸己”,反思自己。...

原创小博客
17分钟前
0
0
大数据教程(9.5)用MR实现sql中的jion逻辑

上一篇博客讲解了使用jar -jar的方式来运行提交MR程序,以及通过修改YarnRunner的源码来实现MR的windows开发环境提交到集群的方式。本篇博主将分享sql中常见的join操作。 一、需求 订单数据表...

em_aaron
25分钟前
1
0
十万个为什么之什么是resultful规范

起源 越来越多的人开始意识到,网站即软件,而且是一种新型的软件。这种"互联网软件"采用客户端/服务器模式,建立在分布式体系上,通过互联网通信,具有高延时(high latency)、高并发等特点...

尾生
31分钟前
1
0
Terraform配置文件(Terraform configuration)

Terraform配置文件 翻译自Terraform Configuration Terraform用文本文件来描述设备、设置变量。这些文件被称为Terraform配置文件,以.tf结尾。这一部分将讲述Terraform配置文件的加载与格式。...

buddie
54分钟前
2
0
exportfs命令, vsftp搭建ftp服务

exportfs命令 当修改/etc/exports文件后,更改的内容是不会立即生效的。如果重启nfs服务,会导致客户端重启期间的请求是挂起等待的,可以把客户端的挂载umount进行卸载后,再重启nfs服务,但...

野雪球
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部