C题：自定义TreeNode内部类，先造树再中序遍历返回结果

public class Main{
    ArrayList<Integer> mid_tree=new ArrayList<>();
    public int[] solve (int n, int[] pre, int[] suf) {
        TreeNode root= build_tree(pre,0,pre.length-1,suf,0,suf.length-1);
        dfs(root);
        return mid_tree.stream().mapToInt(Integer::valueOf).toArray();
    }
    public void dfs(TreeNode node){
        if(node==null) return;
        dfs(node.left);
        mid_tree.add(node.val);
        dfs(node.right);
    }
    private TreeNode build_tree(int[] pre, int left1,int right1,int[] suf,int left2,int right2){
        if(left1>right1||left2>right2) return null;
        TreeNode node=new TreeNode(pre[left1]);//pre[left1]一定等于suf[right2]
        if(left1+1>right1||right2-1<left2) return node;//没有左右子树了
        int left_end=right2-1;
        int right_start=left1+1;
        for(int i=right2-1;i>=left2;i--){//一定有左子树，先把左子树在suf的终点确定下来
            if(suf[i]==pre[left1+1]){
                left_end=i;//左子树在suf的终点
                break;
            }
        }
        if(left_end==right2-1){//只有左子树没有右子树,因为只有一个孩子时认为是左孩子
            node.left=build_tree(pre,left1+1,right1,suf,left2,left_end);
        }
        else{
            //左右子树都有，还得把右子树的界限确定下来
            for(int i=left1+1;i<=right1;i++){
                if(pre[i]==suf[right2-1]){
                right_start=i;//右子树在pre的起始位置
                }
            }
            node.left=build_tree(pre,left1+1,right_start-1,suf,left2,left_end);
            node.right=build_tree(pre,right_start,right1,suf,left_end+1,right2-1);
        }
        return node;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}