Pre- and Post-order Traversals

PAT-1119

• 这题难度较大，主要需要考虑如何实现根据前序遍历和后序遍历来确定一颗二叉树

• 一篇好的文章: 题解

  import java.util.Scanner;

  /**

  • @Author WaleGarrett
  • @Date 2020/9/5 18:04
    */
    public class PAT_1119 {
    static int[] preorder;
    static int[] postorder;
    static boolean flag=true;//判断二叉树是否唯一
    public static void main(String[] args) {
    Scanner scanner=new Scanner(System.in);
    int n=scanner.nextInt();
    preorder=new int[n];
    postorder=new int[n];
    for(int i=0;i=prer)
    return root;
    // System.out.println(prel+" "+prer);
    int position=0;
    if(prel<prer&&preorder[prel+1]==postorder[postr-1]){
    flag=false;//不唯一
    //默认为左子树
    root.left=buildTree(prel+1,prer,postl,postr-1);
    }else{
    for(int i=postl;i<postr;i++){
    // System.out.println(i+" "+(prel+1));
    if(postorder[i]==preorder[prel+1]){
    position=i;
    break;
    }
    }
    int numl=position-postl+1;
    root.left=buildTree(prel+1,prel+numl,postl,position);
    root.right=buildTree(prel+numl+1,prer,position+1,postr-1);
    }
    return root;
    }
    public static String inOrder(PPNode root,String result){
    if(root.left!=null)
    result=inOrder(root.left,result);
    result=result+root.value+" ";
    if(root.right!=null){
    result=inOrder(root.right,result);
    }
    return result;
    }
    }
    class PPNode{
    PPNode left;
    PPNode right;
    int value;
    public PPNode(){
    left=right=null;
    value=-1;
    }
    }