📌문제2. 이진탐색트리 여부 확인

✅ 문제

✅ 아이디어

⭐ 왼쪽 서브트리의 max를 찾는다
⭐ 오른쪽 서브트리의 min을 찾는다
⭐ max < root < min 조건을 만족해야 BST를 만족함
⭐ Recursion 수행하기

✅ minValue, maxValue 함수

✔️ minValue 함수

⚠️ return INT16_MAX; 를 사용하는 이유
: 최소값을 찾는 함수이기 때문에, 노드가 없는 경우에는 아주 큰 값을 반환해서 다른 노드들과 비교했을 때 이 값이 최소값으로 선택되지 않게 함.

int BinaryTree::minValue(BinaryNode* node)
{
   if(node == NULL) return INT16_MAX;
   int value = node->getData();
   int leftMin = minValue(node->getLeft());
   int rightMin = minValue(node->getRight());
   
   return min(value, min(leftMin, rightMin));
}

---

✔️ maxValue 함수

⚠️ return INT16_MIN;을 사용하는 이유
: 16비트 정수의 최솟값을 의미함 --> 이 값은 아주 작은 숫자를 나타내기 때문에, 노드가 없는 경우(node == NULL일 때)에 비교할 수 있는 가장 작은 값으로 반환됨.

int BinaryTree::maxValue(BinaryNode* node)
{
	if(node == NULL) return INT16_MIN;
    int value = node->getData();
    int leftMax = maxValue(node->getLeft());
    int rightMax = maxValue(node->getRight());
    
    return max(value, max(leftMax, rightMax));
 }

✅ isBST 함수

✔️ isBST 함수

bool BinaryTree::isBST(BinaryNode* node)
{
	if(node == NULL) return true;
    if(node->getLeft() != NULL && maxValue(node->getLeft()) >= node->getData()) 
    	return false;
    if(node->getRight() != NULL && minValue(node->getRight()) <= node->getData()) 
    	return false;
    if(!isBST(node->getLeft()) || !isBST(node->getRight())) 	
    	return false;
    return true;
}

✅ 메인 함수

<강의 자료>

int main()
{
	BinaryTree bt;
    int N;
    vector<BinaryNode*> v;
    
    cin >> N;
    v.resize(N+1);
    for(int i = 1; i <= N; i++) 
    	v[i] = new BinaryNode(i);
    for(int i = 0 ; i < N ; i++)
    {
    	char root,left,right;
        cin >> root >> left >> right;
        
        if(left != '.') v[root-'0']->setLeft(v[left-'0']);
        else v[root - '0']->setLeft(NULL)
        
        if(right != '.') v[root-'0']->setRight(v[right-'0']);
        else v[root-'0']->setRight(NULL);
        if(i == 0) bt.setRoot(v[root-'0']);
    }
    // BST인지 확인하기
    if(bt.isBST(bt.getRoot()) cout << "1";
    else cout << "0";
    return 0;
}

---

<내가 짠 코드>

int main() {
	int N;
	char root,left, right;
	vector<BinaryNode*> node;
	BinaryTree tree;

	cin >> N;
	node.resize(N + 1); 

	// 노드 생성 
	for (int i = 1; i <= N; i++) {
		node[i] = new BinaryNode(i);  

	for (int i = 0; i < N; i++) {
		cin >> root >> left >> right;

		if (i == 0) {
			tree.setRoot(node[root]);
		}

		// 왼쪽 자식 설정
		if (left != '.') {
			node[root]->setLeft(node[left-'0']);
		}
		
		// 오른쪽 자식 설정
		if (right != '.') {
			node[root]->setRight(node[right-'0']);
		}
	}

	cout << tree.isBST(tree.getRoot()) << endl;

	return 0;
}

⚠️ char형에 -'0'을 해서 int로 변환해줘야함

• root, left, right은 char형 임!
  ⭐ root -'0' , left - '0' , right - '0' 처럼 0을 빼는 이유
  --> 문자를 정수로 변환하기 위해서
• 문자 '0'의 ASCII 값은 48
  root = '5' 라면 root -'0' 의 값은?
  --> '5'-'0' = 53 - 48 = 5

⚠️ node.resize(); 하는 경우

1) 벡터의 특정 인덱스로 접근하려는 경우
: resize()를 사용해서 벡터의 크기를 정해놓고 시작해야함 --> resize() 안하면 에러남!!
--> vector<BinaryNode*> node;를 선언하면 자동으로 node.resize(N+1); 작업을 해줘야함!!
2) push_back()을 사용하면 resize() X , 특정 인덱스 접근 X
-> 그냥 새로운 요소를 벡터 끝에 추가하므로 크기가 알아서 동적으로 확장됨. 대신 특정 인덱스 접근X
--> 이건 순차적으로 요소를 추가하고 그 순서대로 접근 가능