文档章节

【九度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

没有更多内容

加载失败,请刷新页面

加载更多

下一页

kernel version does not match DSO version

错误信息: kernel version 384.11 does not match DSO version 384.130.0 原因是: cuda driver版本太低,不匹配DSO 简单有效的修复方法,升级nvidia driver, 步骤如下: 1. google seach ...

刘小米
今天
0
0
maven坐标和依赖

一、maven坐标详解 <groupId>com.fgt.club</groupId><artifactId>club-common-service-facade</artifactId><version>3.0.0</version><packaging>jar</packaging> maven的坐标元素说......

老韭菜
今天
1
0
springmvc-servlet.xml配置表功能解释

问:<?xml version="1.0" encoding="UTF-8" ?> 答: xml version="1.0"表示是此xml文件的版本是1.0 encoding="UTF-8"表示此文件的编码方式是UTF-8 问:<!DOCTYPE beans PUBLIC "-//SPRING//......

隐士族隐逸
今天
1
0
基于TP5的微信的公众号获取登录用户信息

之前讲过微信的公众号自动登录的菜单配置,这次记录一下在TP5项目中获取自动登录的用户信息并存到数据库的操作 基本的流程为:微信设置自动登录的菜单—>访问的URL指定的函数里获取用户信息—...

月夜中徘徊
今天
0
0
youTrack

package jetbrains.teamsys.license.runtime; 计算lis package jetbrains.ring.license.reader; 验证lis 安装后先不要生成lis,要把相关文件进行替换 ring-license-checker-1.0.41.jar char......

max佩恩
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部