lintcode - 정렬 그룹을 가장 작은 두 갈래 검색 트리로 변환

1. 제목
정렬 수조 (작은 것부터 큰 것) 를 높이가 가장 작은 정렬 두 갈래 나무로 변환합니다.
주의사항
 There may exist multiple valid solutions, return any of them.
예제
수조 제시[1,2,3,4,5,6,7], 반환

     4
   /   \
  2     6
 / \    / \
1   3  5   7

2. 생각
두 갈래 검색 트리 (두 갈래 정렬 트리라고도 함):
① 아니면 빈 나무 한 그루;
② 또는: 왼쪽 나무가 비어 있지 않으면 왼쪽 나무의 모든 결점의 값이 뿌리 결점의 값보다 작다.
만약 그것의 오른쪽 트리가 비어 있지 않으면 오른쪽 트리의 모든 결점의 값은 그것의 뿌리 결점의 값보다 크다.그것의 왼쪽, 오른쪽 나무도 각각 두 갈래 정렬 나무이다.
————————————————————————————————————————————————————————
정렬 수조를 끊임없이 반복적으로 호출하여 함수 자체를 이분하고 귀속을 통해 각 층의 좌우 트리를 만듭니다... 
주어진 것은 작은 것부터 큰 것까지의 정렬 수조이기 때문에 먼저 이 수조의 중치를 찾아 이 중치를 루트 노드에 부여한다. 이때 중치가 왼쪽의 데이터는 모두 중치보다 작기 때문에 이 수조로 루트 노드의 왼쪽 트리(귀속)를 구축할 수 있고 중치가 오른쪽의 데이터는 모두 중치보다 크면 오른쪽 트리(귀속)를 구축할 수 있다.귀속이 끝나면 두 갈래 검색 트리를 구축하고 왼쪽, 오른쪽 나무도 두 갈래 검색 트리로 나뉜다.
3. 코드
/**  * Definition of TreeNode:  * class TreeNode {  * public:  *     int val;  *     TreeNode *left, *right;  *     TreeNode(int val) {  *         this->val = val;  *         this->left = this->right = NULL;  *     }  * }  */class Solution { public:    /**      * @param A: A sorted (increasing order)array * @return: A tree node */Tree Node * ToBST (vector & T, int a, int c)/호출할 함수,변환 시작 {if(a>c)return NULL;else{intb=(a+c)/2;TreeNode*root=New TreeNode(T[b]);root->left=ToBST(T,a,b-1);root->right=ToBST(T,b+1,c);return root;        }     }         TreeNode *sortedArrayToBST(vector &A) {        //write your code here         if(A.empty())            return NULL;         else           {  int begin=0,end=A.size()-1,mid=(begin+end)/2;              TreeNode *root=new TreeNode(A[mid]);              root->left=ToBST(A,begin,mid-1);//호출 함수 root->right=ToBST(A,mid+1,end);//호출 함수return root;           }         } };
소감
이 문제는 이분법과 귀속에 관련된다.
처음에 if(a>c)return NULL을 if(a>=c)return NULL로 썼는데...26%의 테스트 데이터만 지나고 두 개의 수조 원소만 있을 때 예를 들어 [1,1]-1을 루트 노드로 한 후에 두 번째 층의 수는 NULL로 되돌아왔다. 실제적으로 값이 -1인 노드를 만들어야 한다.