文档章节

【九度OJ1521】|【剑指offer19】二叉树的镜像

aqia358
 aqia358
发布于 2013/12/18 21:13
字数 533
阅读 133
收藏 4
点赞 0
评论 0
题目描述:

输入一个二叉树,输出其镜像。

输入:

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

输出:

对应每个测试案例,
按照前序输出其孩子节点的元素值。
若为空输出NULL。

样例输入:
7
8 6 10 5 7 9 11
d 2 3
d 4 5
d 6 7
z
z
z
z
样例输出:
8 10 11 9 6 7 5
解:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
 
public class Main {
    public int data;
    public Main left = null;
    public Main right = null;
    public static int n;
 
    public Main(int data) {
        this.data = data;
    }
 
    public static Main find(int data, Main root) {
        if (root == null)
            return null;
        if (root.data == data)
            return root;
        Main m = find(data, root.left);
        if (m == null) {
            return find(data, root.right);
        }
        return m;
    }
 
    public static void print(Main root) {
        if (root != null) {
            n--;
            if (n == 0)
                System.out.println(root.data);
            else
                System.out.print(root.data + " ");
            print(root.right);
            print(root.left);
        }
    }
 
    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;
            if (n == 0)
                System.out.println("NULL");
            else {
                int[] array = new int[n];
                for (int i = 0; i < n; i++) {
                    st.nextToken();
                    array[i] = (int) st.nval;
                }
                Main root = new Main(array[0]);
                for (int i = 0; i < n; i++) {
                    Main m = Main.find(array[i], root);
                    st.nextToken();
                    String o = st.sval;
                    if (o.equals("d")) {
                        st.nextToken();
                        int p = (int) st.nval;
                        m.left = new Main(array[p - 1]);
                        st.nextToken();
                        p = (int) st.nval;
                        m.right = new Main(array[p - 1]);
                    } else if (o.equals("l")) {
                        st.nextToken();
                        int p = (int) st.nval;
                        m = Main.find(array[i], root);
                        m.left = new Main(array[p - 1]);
                    } else if (o.equals("r")) {
                        st.nextToken();
                        int p = (int) st.nval;
                        m = Main.find(array[i], root);
                        m.right = new Main(array[p - 1]);
                    }
                }
                Main.n = n;
                Main.print(root);
            }
        }
    }
 
}
/**************************************************************
    Problem: 1521
    User: aqia358
    Language: Java
    Result: Accepted
    Time:340 ms
    Memory:14748 kb
****************************************************************/








© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 81
码字总数 30297
作品 0
海淀
程序员
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴 ⋅ 2017/11/08 ⋅ 0

剑指Offer——知识点储备-常用算法

剑指Offer——知识点储备-常用算法 快速排序 注:若排序是有序的,采用快排,则退化为冒泡排序。 解决这个问题,采用两个选取基准的方法 (1)随机选取基数(在这个区间内随机取一个数) 出现...

sunhuaqiang1 ⋅ 2016/11/07 ⋅ 0

剑指offer:java判断二叉树是否对称

题目 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 解题 两个二叉树的前序遍历一样 同时需要考虑空结点

孟飞阳 ⋅ 2016/06/29 ⋅ 0

剑指Offer算法题

反转二叉树(就是二叉树的镜像) public class Mirror { public void mirrorTree(TreeNode root) { if (null == root) {// 空结点 return; } if (root.left == null && root.right == null)......

gaomq ⋅ 03/02 ⋅ 0

《剑指offer》-判断对称二叉树

题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 思路上还是广度优先搜索(BFS)来做的。BFS是依托于STL的que...

lovedan ⋅ 2017/03/05 ⋅ 0

python剑指offer66题

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

lyy0905 ⋅ 06/03 ⋅ 0

二叉树简单操作(下)

一、二叉树基本操作  1. 求二叉树的深度。(树的深度:树中所有节点的层次的最大值称为该树的深度)  2. 求二叉树叶子结点的个数。(叶子节点:度为0的结点称为叶结点,叶节点也称为终端节点...

qq_38646470 ⋅ 01/22 ⋅ 0

剑指Offer学习总结-重建二叉树

剑指Offer学习总结-重建二叉树 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog.163.co...

wwlcsdn000 ⋅ 01/16 ⋅ 0

Redis研究-3.3数据结构之树与查找、排序等

1.树相关的内容 1.1 Tree概念 树是n(n>=0)个节点的有限集。n=0的时候,我们把它叫做空树。在任何一非空树中满足两个特点:(1)有且只有一个叫做根的节点。(2)n>1时,其余节点可分为m(m>0...

会飞的杨先生 ⋅ 2015/08/26 ⋅ 0

数据结构-二叉树的存储结构与遍历

定义 一个有穷的结点集合,可以为空。若不为空,则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。 二叉树的五种基本形态: tree_state 二叉树的子树是有顺序之分的,称为左...

IAM四十二 ⋅ 2017/10/24 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

6. Shell 函数 和 定向输出

Shell 常用函数 简洁:目前没怎么在Shell 脚本中使用过函数,哈哈,不过,以后可能会用。就像java8的函数式编程,以后获取会用吧,行吧,那咱们简单的看一下具体的使用 Shell函数格式 linux ...

AHUSKY ⋅ 7分钟前 ⋅ 0

MySQL 内核深度优化

MYSQL数据库适用场景广泛,相较于Oracle、DB2性价比更高,Web网站、日志系统、数据仓库等场景都有MYSQL用武之地,但是也存在对于事务性支持不太好(MySQL 5.5版本开始默认引擎才是InnoDB事务...

OSC_cnhwTY ⋅ 14分钟前 ⋅ 0

单片机软件定时器

之前写了一个软件定时器,发现不够优化,和友好,现在重写了 soft_timer.h #ifndef _SOFT_TIMER_H_#define _SOFT_TIMER_H_#include "sys.h"typedef void (*timer_callback_function)(vo...

猎人嘻嘻哈哈的 ⋅ 16分钟前 ⋅ 0

好的资料搜说引擎

鸠摩搜书 简介:鸠摩搜书是一个电子书搜索引擎。它汇集了多个网盘和电子书平台的资源,真所谓大而全。而且它还支持筛选txt,pdf,mobi,epub、azw3格式文件。还显示来自不同网站的资源。对了,...

乔三爷 ⋅ 24分钟前 ⋅ 0

Debian下安装PostgreSQL的表分区插件pg_pathman

先安装基础的编译环境 apt-get install build-essential libssl1.0-dev libkrb5-dev 将pg的bin目录加入环境变量,主要是要使用 pg_config export PATH=$PATH:/usr/lib/postgresql/10/bin 进......

玛雅牛 ⋅ 25分钟前 ⋅ 0

inno安装

#define MyAppName "HoldChipEngin" #define MyAppVersion "1.0" #define MyAppPublisher "Hold Chip, Inc." #define MyAppURL "http://www.holdchip.com/" #define MyAppExeName "HoldChipE......

backtrackx ⋅ 54分钟前 ⋅ 0

Linux(CentOS)下配置php运行环境及nginx解析php

【part1:搭建php环境】 1.选在自己需要安装的安装包版本,wget命令下载到服务器响应目录 http://php.net/releases/ 2.解压安装包 tar zxf php-x.x.x 3.cd到解压目录执行如下操作 cd ../php-...

硅谷课堂 ⋅ 今天 ⋅ 0

Nginx服务架构初探(四):nginx服务器的rewrite功能

nginx服务器的rewrite功能 1.nginx后端服务器组的配置 1>upstream name {…} name是给服务器组限的组名 2>server address [parameters]; address为服务器地址 parame......

余温灬未存 ⋅ 今天 ⋅ 0

layer.prompt使文本框为空的情况下也能点击确定

最近一直在使用layui,但是用到弹出层layer.prompt时,如果文本框是空的话点击确定没有反应,不能向下执行。 但是我又需要空值,看看我原来的代码。 123456789 layer.prompt...

孟飞阳 ⋅ 今天 ⋅ 0

Linux普通文件压缩工具gzip、Bzip2、xz

第六章 文件压缩和打包 6.1 压缩打包介绍 Linux环境常见压缩文件类型: .zip,.gz,.bz2,.xz, .tar.gz,.tar.bz2,.tar.xz 压缩打包的目的 方便文件传输 节省磁盘空间 减少传输花费的时间 ...

弓正 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部