어흥
[해커랭크] Is This a Binary Search Tree? (C++) 본문
문제 링크: www.hackerrank.com/challenges/is-binary-search-tree/problem
1.주의할 점
- BST의 조건에 대해 정확히 알고 있어야한다. 특정 Node를 기준으로 왼쪽의 Subtree들의 값은 특정노드의 값보다 전부 작아야하고, 오른쪽의 Subtree들은 특정노드의 값보다 전부 커야한다
2. 구현
1) [실패했던 방법]
- 특정 Node를 기준으로 왼쪽에 tree가 있다면, 왼쪽 자식의 값과 현재 값을 비교
- 특정 Node를 기준으로 오른쪽에 tree가 있다면, 오른쪽 자식의 값과 현재 값을 비교
vector<int> v;
bool checkBST(Node* root) {
bool result = true;
if(root->left !=nullptr){
if(root->left->data < root->data)
result = result & checkBST(root->left);
else
result = false;
}
if(root->right !=nullptr){
if(root->data < root->right->data)
result = result & checkBST(root->right);
else
result = false;
}
return result;
}
실패했던 원인: 현재 Node의 왼쪽 Subtree의 값은 모두 현재 값보다 작아야하고, 현재 Node의 오른쪽 Subtree의 값은 모두 현재 값보다 커야 한다
반례)
3
1
4
-> 정답은 False지면 True를 반환한다
2) [위의 코드 수정 -> 정답]
- 해당 Node의 자식값과 비교 -> 해당 Node의 자식 트리와 비교하도록 설정
- isBST() 함수는 3개의 변수를 파라미터로 받으며, 각각 subtree, subtree root의 최소범위, subtree root의 최대범위를 뜻한다
- 왼쪽 subtree의 경우, 항상 현재 root보다 작은 값을 가져야하므로 현재 값을 왼쪽 subtree의 high로 설정한다
- 오른쪽 subtree의 경우, 항상 현재 root보다 큰 값을 가져야하므로 현재 값을 오른쪽 subtree의 low로 설정한다
bool isBST(Node* root, int low, int high){
if(root->data <= low || root->data >= high) return false;
bool result = true;
if(root->left!=nullptr){
result &= isBST(root->left,low,root->data);
}
if(root->right!=nullptr)
result &= isBST(root->right,root->data,high);
return result;
}
3) [참고했던 다른 풀이]
- BST의 경우, inorder로 값을 출력했을 때 오름차순으로 정렬되어야 한다
- inorder의 방식으로 V 벡터에 값을 담으며, 중간의 CheckBST값은 무시하고 모든 Node를 방문했을때 V벡터가 오름차순으로 정렬되어있지 않으면 False를, 되어있다면 True를 반환하도록 한다(검사하는 함수는 매번 작동하지만 맨 처음에 호출된 checkBST의 값만 반환하기때문에 상관X)
vector<int> v;
bool checkBST(Node* root) {
if(root->left !=nullptr)
checkBST(root->left);
v.push_back(root->data);
if(root->right !=nullptr)
checkBST(root->right);
for(int i=0;i<v.size()-1;i++)
if(v[i]>=v[i+1]) return false;
return true;
}
'알고리즘 > HackerRank' 카테고리의 다른 글
[해커랭크] Insert a node at the head of a linked list (C++) (0) | 2021.01.14 |
---|---|
[해커랭크] Inserting a Node Into a Sorted Doubly Linked List (C++) (0) | 2021.01.14 |
[해커랭크] Sparse Arrays (C++) (0) | 2021.01.08 |
[해커랭크] Reverse a doubly linked list (C++) (0) | 2021.01.08 |
[해커랭크] Snakes and Ladders: The Quickest Way Up (C++) (0) | 2021.01.05 |