文档章节

【九度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 58. 对称的二叉树

题目描述 请实现一个函数,用来判断一颗二叉树是不是对称的。注意,如果一个二叉树同此二叉树的镜像是同样的,定义其为对称的。 思路: 二叉树镜像相同是对称的,利用递归做。 参考答案: No...

dby_freedom
11/25
0
0
[剑指offer] 二叉树的镜像

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

繁著
06/29
0
0
算法之路

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

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

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

繁著
07/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Ubuntu16.04下安装docker

[TOC] 本文开发环境为Ubuntu 16.04 LTS 64位系统,通过apt的docker官方源安装最新的Docker CE(Community Edition),即Docker社区版,是开发人员和小型团队的理想选择。 1. 开始安装 1.1 由于...

豫华商
今天
9
0
使用XShell工具密钥认证登录Linux系统

如果你是一名Linux运维,那么Linux服务器的系统安全问题,可能是你要考虑的,而系统登录方式有两种,密码和密钥。哪一种更加安全呢? 无疑是后者! 这里我为大家分享用Xshell利器使用密钥的方...

dragon_tech
今天
7
0
day178-2018-12-15-英语流利阅读-待学习

“真蛛奶茶”了解一下?蜘蛛也会产奶了 Lala 2018-12-15 1.今日导读 “蛋白质含量是牛奶的 4 倍,并有着更低的脂肪和含糖量”,听起来诱人又美味的并不是羊奶或豆奶,而是你可能打死都想不到...

飞鱼说编程
今天
11
0
npm WARN optional SKIPPING OPTIONAL DEPENDENCY: fsevents

场景重现 npm install --verbose 安装依赖的时,出现如下警告 强迫症患者表示不能接受 npm WARN optional SKIPPING OPTIONAL DEPENDENCY: fsevents@1.2.4 (node_modules\fsevents):npm WARN......

taadis
今天
2
0
OSChina 周六乱弹 —— 你一口我一口多咬一口是小狗

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @达尔文 :分享Roy Orbison的单曲《She's a Mystery to Me》 《She's a Mystery to Me》- Roy Orbison 手机党少年们想听歌,请使劲儿戳(这里...

小小编辑
今天
452
6

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部