文档章节

【九度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
海淀
程序员
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
[剑指offer] 二叉树的镜像

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

繁著
06/29
0
0
算法之路

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

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

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

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

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

sunhuaqiang1
2016/11/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java序列化(四) - 实现Externalnalizable接口

实现Externalnalizable接口 实现Externalnalizable接口 package meng.springboot.demo.obj;import java.io.Externalizable;import java.io.IOException;import java.io.ObjectInput......

晨猫
3分钟前
0
0
php 日志库获取调用方的代码文件地址和代码行数

在使用其他语言的打印日志的时候,经常能看到打印日志时带上文件地址和代码行数,对于调试和查找问题非常方便,但是 php 日志库里则很少见到这个功能,但这个功能还是可以实现的。 关键点就是...

anoty
9分钟前
3
0
Android Studio如何批量导入全部包import

当需要导包时,Android Studio有单个导包快捷键 Alt+Enter 但是没有全部的包 但是可以在设置里设置Auto Import自动导入功能

lanyu96
11分钟前
0
0
六款优秀的 Linux 基准测试工具

基准测试是指运行计算机程序去评估硬件和软件性能的行为。硬件基本测试包括评估处理器,内存,显卡,硬盘,网络等不同组件的性能。基准测试有两类: 复合和应用。复合基准对一个硬件执行压力...

openthings
13分钟前
0
0
什么是阿里云容器服务?

关于阿里云容器服务的详细内容:阿里云容器服务使用教程 容器服务(Container Service)提供高性能可伸缩的容器应用管理服务,支持用 Docker 容器进行应用生命周期管理,提供多种应用发布方式...

mcy0425
14分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部