Is It a Binary Search Tree

PAT-1043

主要涉及到根据前序遍历序列片段是否是一颗二叉树，这里有一个小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;

    }

}

巴特西

PAT-1043（Is It a Binary Search Tree）JAVA实现

Is It a Binary Search Tree

PAT-1043

最新文章

热门文章