[LeetCode] Validate Binary Search Tree 풀어보기

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

Validate Binary Search Tree - LeetCode

 

이번에는 BST를 Search하는 문제입니다.

 

문제의 조건은 BST가 적절하게 구성되어있는지인데, 다행히도 기본적으로 left와 right로 구성되어있는 착한 구조체를 가졌습니다.

 

시작 지점이 포인터로 주어지기 때문에 이를 활용해서 dfs형식으로 재귀탐색하면 되겠네요.

 

단순히 현재 위치의 node->left->val이 node->val보다 작은지, node->right->val이 node->val보다 큰지만 비교하면 아래와 같은 케이스를 대비할 수 없습니다.

 

 

따라서 재귀에는 현재 노드에서 가질 수 있는 최솟값, 최댓값을 저장할 변수가 필요합니다.

다만 기본적으로 제공되는 isValidBST의 파라미터를 수정하거나 TreeNode의 멤버를 수정할 수 없기 때문에 새로운 재귀함수를 만들어 사용했습니다.

 

class Solution {
public:
    bool isValidBST(TreeNode* root) {

        return isValidBSTRecursive(root, INT_MIN, INT_MAX);
    }

    bool isValidBSTRecursive(TreeNode* root, int minval, int maxval)
    {
        if (root == nullptr)
            return true;

        if (root->val <= minval || root->val >= maxval)
            return false;

        if (!isValidBSTRecursive(root->left, minval, root->val))
            return false;

        if (!isValidBSTRecursive(root->right, root->val, maxval))
            return false;

        return true;
    }
};

처음에는 이렇게 진행했는데 경계값에 걸려서 

 

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return isValidBSTRecursive(root, LLONG_MIN, LLONG_MAX);
    }

    bool isValidBSTRecursive(TreeNode* root,
                             long long minval,
                             long long maxval)
    {
        if (root == nullptr)
            return true;

        if (root->val <= minval || root->val >= maxval)
            return false;

        if (!isValidBSTRecursive(root->left, minval, root->val))
            return false;

        if (!isValidBSTRecursive(root->right, root->val, maxval))
            return false;

        return true;
    }
};

널널하게 변경하여 통과했습니다.