美文网首页
Poj 2255 Tree Recovery

Poj 2255 Tree Recovery

作者: 少寨主的互联网洞察 | 来源:发表于2018-11-08 17:00 被阅读0次
  • 关于二叉树的前中后序遍历的很好一道题
  • 题目:根据二叉树的前序和中序序列来重建二叉树,输出其后序序列


    image.png
  • 来看看代码描述
package someTest;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.Scanner;

public class POJ2255 {
    private static String last;
    //构建二叉树,并返回根节点
    private static Node1 constructCore(String before,String middle) {
        if("".equals(before)||"".equals(middle)||before.length()<0) {
            return null;
        }
        Node1 root=new Node1();
        char temp=before.charAt(0);
        int rootMiddleIndex=middle.indexOf(temp);
        root.value=temp;
        root.left=constructCore(before.substring(1, rootMiddleIndex)+1, middle.substring(0, rootMiddleIndex));
        root.right=constructCore(before.substring(rootMiddleIndex+1), middle.substring(rootMiddleIndex)+1);
        return root;
    }
    //后序遍历
    private static void lastOrder(Node1 root) {
        if(root==null) {
            return;
        }
        lastOrder(root.left);
        lastOrder(root.right);
        last+=root.value;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        String before;
        String middle;
        while (in.hasNext()) {
            before = in.next();
            middle = in.next();
            Node1 root = constructCore(before, middle);  // 重建之后的二叉树根结点
            last = "";
            lastOrder(root);
            out.println(last);
        }
        out.flush();
    }
}
class Node1{
    public Node1 left;
    public Node1 right;
    public char value;
}

相关文章

  • Poj 2255 Tree Recovery

    关于二叉树的前中后序遍历的很好一道题 题目:根据二叉树的前序和中序序列来重建二叉树,输出其后序序列image.pn...

  • POJ 2255 Tree Recovery(根据前中序遍历,重

    题意:给出二叉树的前序遍历和中序遍历,求后序遍历。 NO.1:无需重建二叉树,可直接求出后序遍历结果。 NO.2 ...

  • POJ 2255(水题)

    题目LINK 题意解释 这道题的意思简单的概述就是给出二叉树的前序遍历和中序遍历,让你输出后续遍历。 收获 这道题...

  • 536 - Tree Recovery

    给出二叉树的先序遍历和中序遍历,求后序遍历。树中结点是不重复的大写字母,因此可以直接用其ASCII码作为数组下标来...

  • POJ 1741 Tree

    Description Give a tree with n vertices,each edge has a l...

  • POJ 1741 Tree

    难度 尚未评定Description给定一颗有个节点的树,每条边有一个权值。树上两个节点和之间的路径长度就是路径上...

  • POJ1308(Is It A Tree?)

    链接:https://vjudge.net/problem/POJ-1308思路:放在并查集专题的,思路是每次合并...

  • Chapter9——图——最小生成树

    1. 题目列表 POJ1789(prim算法) POJ2485(prim) POJ1258(prim) POJ30...

  • poj来自群

    OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj...

  • Chapter5——数据结构——字符串

    1. 题目列表 poj1035,poj3080,poj1936 2. POJ1035——Spell checker...

网友评论

      本文标题:Poj 2255 Tree Recovery

      本文链接:https://www.haomeiwen.com/subject/zwwwxqtx.html