文档章节

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

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

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

输入:

输入可能包含多个测试样例,输入以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
博文 82
码字总数 30297
作品 0
海淀
程序员
算法之路

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

李序锴
2017/11/08
0
0
[剑指offer] 二叉树的镜像

题目描述 操作给定的二叉树,将其变换为源二叉树的镜像。 输入描述: 解题思路 通过对以上两棵树的观察,我们可以总结出这两棵树的根节点相同,但它们的左、右两个子节点交换了位置。所以我们...

繁著
06/29
0
0
[剑指offer] 对称的二叉树

本文首发于我的个人博客:尾尾部落 题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 解题思路 法一:递归。根节...

繁著
07/27
0
0
剑指Offer——知识点储备-常用算法

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

sunhuaqiang1
2016/11/07
0
0
剑指offer:java判断二叉树是否对称

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

孟飞阳
2016/06/29
30
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

JS:异步 - 面试惨案

为什么会写这篇文章,很明显不符合我的性格的东西,原因是前段时间参与了一个面试,对于很多程序员来说,面试时候多么的鸦雀无声,事后心里就有多么的千军万马。去掉最开始毕业干了一年的Jav...

xmqywx
今天
0
0
Win10 64位系统,PHP 扩展 curl插件

执行:1. 拷贝php安装目录下,libeay32.dll、ssleay32.dll 、 libssh2.dll 到 C:\windows\system32 目录。2. 拷贝php/ext目录下, php_curl.dll 到 C:\windows\system32 目录; 3. p...

放飞E梦想O
今天
0
0
谈谈神秘的ES6——(五)解构赋值【对象篇】

上一节课我们了解了有关数组的解构赋值相关内容,这节课,我们接着,来讲讲对象的解构赋值。 解构不仅可以用于数组,还可以用于对象。 let { foo, bar } = { foo: "aaa", bar: "bbb" };fo...

JandenMa
今天
1
0
OSChina 周一乱弹 —— 有人要给本汪介绍妹子啦

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享水木年华的单曲《中学时代》@小小编辑 手机党少年们想听歌,请使劲儿戳(这里) @须臾时光:夏天还在做最后的挣扎,但是晚上...

小小编辑
今天
18
4
centos7安装redis及开机启动

配置编译环境: sudo yum install gcc-c++ 下载源码: wget http://download.redis.io/releases/redis-3.2.8.tar.gz 解压源码: tar -zxvf redis-3.2.8.tar.gz 进入到解压目录: cd redis-3......

hotsmile
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部