Is It a Binary Search Tree

• 主要涉及到根据前序遍历序列片段是否是一颗二叉树，这里有一个小tip就是插入序列就是二叉树的前序遍历序列。

• 第二个是会对排序二叉树进行前序遍历，后序遍历，镜像排序二叉树的前序遍历，后序遍历等操作。

• 题目的整体难度不大，但是对二叉树和二叉排序树的了解需要较深。

  /**

  • @Author WaleGarrett
  • @Date 2020/9/5 8:20
    */

  import java.util.Scanner;

  /**

  • PAT-1043,1064,1066,1086,1089,1099,1098

  • 7

  • 8 6 5 7 10 8 11
    */
    public class PAT_1043 {
    static final int maxn=1003;

    public static void main(String[] args) {
    BinaryTree binaryTree=new BinaryTree();
    Scanner scanner=new Scanner(System.in);
    String result="";
    int n=scanner.nextInt();
    while(n!=0){
    int value=scanner.nextInt();
    binaryTree.insert(value);//插入输入串
    result=result+value+" ";
    n--;
    }
    //使用前序遍历该构建完成的排序二叉树，并且对该树的镜像二叉树进行前序遍历，任何一个序列和题目的序列匹配则说明符合要求，再输出该排序二叉树的后序遍历
    String preorder=binaryTree.preOrder(binaryTree.root,"");//前序遍历
    String mpreorder=binaryTree.mPreOrder(binaryTree.root,"");//镜像前序遍历
    if(preorder.equals(result)){
    System.out.println("YES");
    System.out.println(binaryTree.postOrder(binaryTree.root,"").trim());
    }else if(mpreorder.equals(result)){
    System.out.println("YES");
    System.out.println(binaryTree.mPostOrder(binaryTree.root,"").trim());
    }else
    System.out.println("NO");
    }
    }
    class Node{
    Node left;
    Node right;
    int value;
    public Node(){
    left=right=null;
    value=-1;
    }
    public Node(Node left,Node right,int value){
    this.value=value;
    this.left=left;
    this.right=right;
    }
    }
    class BinaryTree{
    Node root;
    public BinaryTree(){
    root=null;
    }
    public void insert(int value){
    if(root==null){
    root=new Node();
    root.value=value;
    }else{
    Node now=root;
    while(true){
    if(value<now.value){
    if(now.left==null){
    now.left=new Node(null,null,value);
    break;
    }else now=now.left;
    }else{
    if(now.right==null){
    now.right=new Node(null,null,value);
    break;
    }else{
    now=now.right;
    }
    }
    }
    }
    }
    public String preOrder(Node now,String result){
    result=result+now.value+" ";
    Node left=now.left;
    if(left!=null){
    result=preOrder(left,result);
    }
    Node right=now.right;
    if(right!=null){
    result=preOrder(right,result);
    }
    return result;
    }
    public String mPreOrder(Node now,String result){
    result=result+now.value+" ";
    Node right=now.right;
    if(right!=null){
    result=mPreOrder(right,result);
    }
    Node left=now.left;
    if(left!=null){
    result=mPreOrder(left,result);
    }
    return result;
    }
    public String postOrder(Node now,String result){
    Node left=now.left;
    if(left!=null){
    result=postOrder(left,result);
    }
    Node right=now.right;
    if(right!=null){
    result=postOrder(right,result);
    }
    result=result+now.value+" ";
    return result;
    }
    public String mPostOrder(Node now,String result){

    Node right=now.right;
    if(right!=null){
        result=mPostOrder(right,result);
    }
    Node left=now.left;
    if(left!=null){
        result=mPostOrder(left,result);
    }
    result=result+now.value+" ";
    return result;

    }
    }