import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int in[]=new int[n];
int pre[]=new int[n];
for(int i=0;i<n;i++){
pre[i]=sc.nextInt();
}
for(int i=0;i<n;i++){
in[i]=sc.nextInt();
}
Main m=new Main();
BST tree=m.new BST();
tree.construct(pre,in);
System.out.println(tree.maxSize());
}
class BST{
class Node{
Node left;
Node right;
int data;
}
Node root;
public void construct(int pre[], int in[]){
this.root=this.construct(pre,0,pre.length-1,in,0,in.length-1);
}
private Node construct(int pre[], int plo, int phi, int in[],int ilo, int ihi){
if(plo>phi||ilo>ihi){
return null;
}
int index=0;
Node nn=new Node();
nn.data=pre[plo];
for(int i=ilo;i<=ihi;i++){
if(in[i]==pre[plo]){
index=i;
break;
}
}
nn.left=construct(pre,plo+1,plo+index,in,ilo,index-1);
nn.right=construct(pre,plo+index+1,phi,in, index+1,ihi);
return nn;
}
public boolean isBST(Node node){
return this.isBST(node,Integer.MIN_VALUE,Integer.MAX_VALUE);
}
private boolean isBST(Node node, int min, int max){
if(node==null)
return true;
if(node.data>max||node.data<min){
return false;
}
else if(!this.isBST(node.left,min,node.data)){
return false;
}
else if(!this.isBST(node.right,node.data,max)){
return false;
}
return true;
}
private int size(Node node){
if(node==null)
return 0;
return (size(node.left)+size(node.right))+1;
}
public int maxSize(){
return this.maxSize(this.root);
}
private int maxSize(Node root){
if(isBST(root)){
return size(root);
}
return Math.max(maxSize(root.left),maxSize(root.right));
}
}
}Not passing test cases, please check my code
Hey
try for this input :
9
50 30 5 20 60 45 70 65 80
5 30 20 50 45 60 65 70 80
correct output : 5
Debug for this