PreOrder에서 이진 검색 트리 구성

Question

preorderTransaversal에서 이진 검색 트리를 구성하는 방법. 제안 사항이 있으면 제안하십시오.

Node constructTreeFromPreorder(int[] arr,int start,int end) 
{ 
if(arr==null){ 
    return null; 
}else{ 
    if(start>end){ 
     return null; 
    } 
    int element=arr[start]; 
    Node node=new Node(element); // create node 
    if(start==end){ 
     return node; 
    } 
    int index=start+1; 
    for(int i=index;i<=end;i++){ 
      index=i; 
     if(arr[i]>element){ 
      break; 
     } 
    } 
    node.left=constructTreeFromPreorder(arr, start+1, index-1); 
    node.right=constructTreeFromPreorder(arr, index, end); 
    return node; 
} 

Answer 1

선주문 순회에 해당하는 여러 이진 트리가 있습니다. 예를 들어 선주문 통과 [2,1,3]을 고려해보십시오. 즉,이 나무의 모든의 전순 주사입니다 :

2   2  2   2  2 
1 3  1   1  1   1 
     3   3   3   3 

당신이 유일하게 이진 트리를 설명하려는 경우 그냥 전순 주사보다 더 많은 정보가 필요합니다.

질문을 수정 한 후에 추가 : 그 중 첫 번째 만 유효한 이진 검색 트리입니다. 주어진 선주문 통과에 대해 여러 개의 BST가 있는지 확실하지 않습니다.

목록에 중복 항목이있는 경우 어떤 사전 주문 순회에 대해 여러 개의 트리가있을 수 있습니다.