본문 바로가기
Algorithm🐰/리트코드

[리트코드] 98. Validate Binary Search Tree - BT

by Jouureee 2021. 8. 17.

문제 :

https://leetcode.com/problems/validate-binary-search-tree/

 

Validate Binary Search Tree - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

예시 :

Input: root = [5,1,4,null,null,3,6]

Output: false

Explanation: The root node's value is 5 but its right child's value is 4.

 

주어진 input이 이진트리인지 확인하는 문제 

 

일단 드는 생각은 input 배열을 돌면서 루트에 대해 left, right가 null이 아니게 있는지 확인하면 될거 같다. 

(+ 각 루트 노드 돌면서 왼쪽값 < 루트값 < 오른쪽 값 크기 순을 유지해야 한다)

 

근데 문제가 TreeNode 구조체를 이용하도록 되어있어서 일단 거부감이 든다 .. 겁 먹지 말자 !!

recursive하게와 DFS하게 풀면 될거 같다는 생각은 들었는데 접근을 어떻게 해야 할지 우선 차근 차근 생각해보자

 

1) DFS 

class Solution {

public:
    void helper(TreeNode* root, vector<int> &inorder){
        if(root == nullptr){
            return;
        }
        
        helper(root->left, inorder);
        inorder.push_back(root->val);
        helper(root->right, inorder);
    }
    
    bool isValidBST(TreeNode* root) {
        vector<int> inorder;
        helper(root, inorder);
        
        for(int i= 1; i < inorder.size(); i++){
            if(inorder[i-1] >= inorder[i]){
                return false;
            }
        }
        
        return true;
    }

};

inorder 순으로 node들을 담는다. 담는 함수 helper는 재귀로 하여 inorder순을 유지한다.

 

isValid에서 이를 하나 하나 돌며 값 비교 하여 이진 트리인지 확인한다.

 

2) Recursive

class Solution {

public:
    TreeNode* previous = nullptr;
    //recursive
     bool isValidBST(TreeNode* root) {
         if(root == nullptr){
             return true;
         }
        
         if (!isValidBST(root->left)) {
             return false;
         }

         if (previous && previous->val >= root->val) {
             return false;
         }
        
         previous = root;
        
         return isValidBST(root->right);
 
     }
}

previous는 위의 inorder와 같은 역할을 한다. previous가 만들어지고 나서야 3번째 if문을 들어설 수 있다. for문을 통해 inorder의 값의 크기를 비교했던 것 처럼 if문과 같은 역할을 하는데 false되지 않으면 마지막으로 right 값까지 비교를 다 마친 후 종료하게 된다.

 

메모리 효율도는 비슷하지만 run time은 위의 코드가 조금 더 앞섰다 ..! ! 둘다 하지만 재귀를 기반으로 한다는 점에서 비슷한 거 같다.

댓글