文档章节

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

aqia358
 aqia358
发布于 2013/12/24 09:35
字数 612
阅读 74
收藏 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
海淀
程序员
python剑指offer66题

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

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

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

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

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

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

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

繁著
06/30
0
0
编程题——21~30

二十一、包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中,调 用min、push及pop的时间复杂度都是O(1)。 二十二、栈的压入、弹出序列 输入两...

thanatos_y
2016/07/22
1
0

没有更多内容

加载失败,请刷新页面

加载更多

中国移动蔡谦:5G传输准备就绪

目前5G已成业界热议话题,在即将到来的万物互联时代,5G是非常关键的技术。且5G相比4G,业务场景多种多样,对5G承载网带来巨大挑战。5G传输,承载先行并不仅仅是一个口号。当前5G承载网的部署...

linux-tao
32分钟前
4
0
维护“修理权”,苹果使用专有软件工具来修复MacBook Pro和iMac Pro

根据上月发给苹果授权服务提供商的一份文件,苹果公司正在使用新的专有软件诊断工具来修复MacBook Pros和iMac Pros,如果不用专有软件工具来修复关键部件,将会导致“系统失效和修复不完整”...

linuxCool
今天
2
0
cacti监控安装

cacti是用PHP实现的一个软件,它用snmp服务获取数据,然后用rrdtool存储和更新数据,并生成图表展示。比较适合用于交换机、路由器的网络监控,插件众多,可图示化显示网络状况。 cacti官方推...

hiwill
今天
4
0
shell特殊符号、cut、sort、uniq、wc、tee、tr、split命令

10月15日任务 8.10 shell特殊符号cut命令 8.11 sort_wc_uniq命令 8.12 tee_tr_split命令 8.13 shell特殊符号下 cut 命令 cut作用:截取字符串 用法如下:cat /etc/passwd |head -2 |cut -d ...

hhpuppy
今天
4
0
Springboot实现filter拦截token验证和跨域

背景 web验证授权合法的一般分为下面几种 1使用session作为验证合法用户访问的验证方式 使用自己实现的token 使用OCA标准 在使用API接口授权验证时,token是自定义的方式实现起来不需要引入其...

funnymin
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部