LeetCode : 98. Validate Binary Search Tree

dfs와 트리를 결합한 문제이다.

Binary Search Tree의 특징에 대해 잘 이해하고 Tree의 Traversal이 어떻게 이루어지는 지 잘 이해하고 있으면

쉽게 풀이할 수 있다.

 

[메인 로직]

root->left, root->val, root->right순으로 dfs를 진행했다. 즉, Inorder Traversal을 통해 문제를 해결했다.

여기서 핵심은, BST의 경우 Inorder Traversal을 했을 때에 모든 값들이 오름 차순 정렬이 되어 있어야 한다는 것이다!

root->val값들을 모두 vector에 저장해놓은 후, v[v.size()-1]의 값과 비교하여 이 값보다 작다면 무조건 false를 반환하도록 했다.

 

class Solution {
public:
    bool check = true;
    vector<int> v;
    
    // Inorder Traversal
    void Traversal(TreeNode *root){
        if(check==false) return;
        
        if(root->left!=NULL){
            Traversal(root->left);
        }
        
        if(v.size()==0){
            v.push_back(root->val);
        }else{
            if(v[v.size()-1]>=root->val){
                check = false;
                return;
            }else{
                v.push_back(root->val);
            }
        }
        
            
        if(root->right!=NULL){
            Traversal(root->right);
        }
    }
    
    bool isValidBST(TreeNode* root) {
        Traversal(root);       
        
        return check;
    }
};