Jobdu-1078.Binary Tree Traverse

Posted on | In

Jobdu-1078-二叉树遍历

Question

题目描述：

二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。

输入：

两个字符串，其长度n均小于等于26。第一行为前序遍历，第二行为中序遍历。二叉树中的结点名称以大写字母表示：A，B，C….最多26个结点。

输出：

输入样例可能有多组，对于每组测试样例，输出一行，为后序遍历的字符串。

样例输入：

ABCBACFDXEAGXDEFAG

样例输出：

BCAXEDGAF

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.Scanner;
public class MyClass {
    static class Node{
        int val;
        Node left;
        Node right;
    }
    public static Node getRoot(String pre, String mid){
        if(pre.length() == 0)
            return null;
        Node node = new Node();
        char root = pre.charAt(0);
        int pos = mid.indexOf(root);
        
        String preLeft = pre.substring(1, pos+1);
        String preRight = pre.substring(pos+1);
        String midLeft = mid.substring(0, pos);
        String midRight = mid.substring(pos+1);
        
        node.val = root;
        node.left = getRoot(preLeft, midLeft);
        node.right = getRoot(preRight, midRight);
        return node;
    }
    public static void postOrder(Node node){
        if(node.left != null)
            postOrder(node.left);
        if(node.right != null)
            postOrder(node.right);
        System.out.print(node.val);
        
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String pre = sc.next();
            String mid = sc.next();
            Node node = getRoot(pre, mid);
            postOrder(node);
            System.out.println();
        }
        
    }
}