二叉树后序遍历

import java.util.Scanner;

/**
 * @Author: coderjjp
 * @Date: 2020-04-24 17:06
 * @Description: 二叉树后序遍历
 * @version: 1.0
 */
public class Main {
    private static void getTree(String pre, int preL, int preR, String mid, int midL, int midR) {
        if (preL>preR)
            return ;
        if (preL==preR){
            System.out.print(pre.charAt(preL));
            return;
        }
        for (int i=midL;i<=midR;i++){
            if (pre.charAt(preL)==mid.charAt(i)){
               getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
               getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
            }
        }
        System.out.print(pre.charAt(preL));
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String pre = sc.next();
        String mid = sc.next();
        getTree(pre,0,pre.length()-1,mid,0,mid.length()-1);
        sc.close();
    }
}

import java.util.Scanner;
 
/**
 * @Author: coderjjp
 * @Date: 2020-04-24 17:06
 * @Description: 二叉树后序遍历
 * @version: 1.0
 */
public class Main {
    private class TreeNode{
        TreeNode left;
        TreeNode right;
        char val;
        public TreeNode(char val) {
            this.val = val;
        }
    }
 
    public StringBuilder getLast(char[] pre,char[] mid){
        TreeNode root = getTree(pre,0,pre.length-1,mid,0,mid.length-1);
        StringBuilder sb = new StringBuilder();
        lastSort(root,sb);
        return sb;
    }
 
    private TreeNode getTree(char[] pre, int preL, int preR, char[] mid, int midL, int midR) {
        if (preL>preR)
            return null;
        if (preL==preR)
            return new TreeNode(pre[preL]);
        TreeNode root = new TreeNode(pre[preL]);
        for (int i=midL;i<=midR;i++){
            if (pre[preL]==mid[i]){
                root.left=getTree(pre,preL+1,i-midL+preL,mid,midL,i-1);
                root.right=getTree(pre,i-midL+preL+1,preR,mid,i+1,midR);
            }
        }
        return root;
    }
 
    private void lastSort(TreeNode root, StringBuilder sb) {
        if (root==null)
            return;
        lastSort(root.left,sb);
        lastSort(root.right,sb);
        sb.append(root.val);
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] pre = sc.next().toCharArray();
        char[] mid = sc.next().toCharArray();
        StringBuilder last = new Main().getLast(pre,mid);
        System.out.println(last);
        sc.close();
    }
}

import java.util.*;
class TreeNode{
    char val;
    TreeNode left = null;
    TreeNode right = null;
    TreeNode(char val) { this.val = val;}
}
public class Main{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()){
            String[] str = sc.nextLine().split(" ");
            char []pre = str[0].toCharArray();
            char []in = str[1].toCharArray();
            TreeNode root = reCon(pre, in);
            find(root);
        }
    }
    public static TreeNode reCon(char[] pre, char[] in){
        if (pre.length==0||in.length==0)
            return null;
        TreeNode root = new TreeNode(pre[0]);
        for (int i=0;i<in.length;i++)
            if (in[i]==pre[0]){
                root.left = reCon(
                Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reCon(
                Arrays.copyOfRange(pre,i+1,in.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        return root;
    }
   //递归后序遍历方法：
    public static void find(TreeNode root){
        if (root == null) return;
        find(root.left);
        find(root.right);
        System.out.print(root.val);
    }
/*    非递归后序遍历方法：
    public static void find(TreeNode root){
        if (root == null) return;
        TreeNode pCur = root;
        TreeNode pLastVisit = null;
        Stack<TreeNode> stack = new Stack<>();
        while (pCur != null){
            stack.push(pCur);
            pCur = pCur.left;
        }
        while (!stack.isEmpty()){
            pCur = stack.pop();
            if (pCur.right == null||pLastVisit == pCur.right){
                System.out.print(pCur.val);
                pLastVisit = pCur;
            }
            else {
                stack.push(pCur);
                pCur = pCur.right;
                while(pCur != null){
                    stack.push(pCur);
                    pCur = pCur.left;
                }
            }
        }
     }
*/
}