어흥

[해커랭크] Is This a Binary Search Tree? (C++) 본문

알고리즘/HackerRank

[해커랭크] Is This a Binary Search Tree? (C++)

라이언납시오 2021. 1. 11. 16:37
728x90
반응형

문제 링크: www.hackerrank.com/challenges/is-binary-search-tree/problem

 

Is This a Binary Search Tree? | HackerRank

Given the root of a binary tree, you have to tell if it's a binary search tree.

www.hackerrank.com

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;
	}
728x90
반응형
Comments