Skip to content

leet code

2874 - Validate Binary Search Tree

제가 단순히 생각했던 것은

BST를 순회하면서 divide and conquer 방법으로 풀려고 했습니다.

preorder search를 하는 방식으로..!!

그런데 더 좋은 방식이 있다는 것을 다른 솔루션을 보고 알았습니다.

1) inorder search를 하면서 바로 직전의 값을 저장해 두고, 그 값보다 바로 다음 노드의 값이 작으면 invalid로 판단하고,

2) 각 노드에서는 왼쪽, 오른쪽을 보면서 한 번 더 validation을 체크하면 훨씬 더 알고리즘을 단순하게 만들 수 있습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        long leftLimit = -((long)1<<32);
        long rightLimit = ((long)1<<32);

        if(!root->left && !root->right) return true;

        return _isValidBST(root, leftLimit, rightLimit);
    }

    bool _isValidBST(TreeNode* root, long leftLimit, long rightLimit)
    {
        if(root==nullptr) return true;

        // printf("leftLimit: %d\n", leftLimit);
        // printf("value: %d\n", root->val);
        // printf("rightLimit: %d\n", rightLimit);

        bool left = true;
        bool right = true;

        if(root->val < leftLimit) return false;
        if(root->val > rightLimit) return false;

        if(root->left)
        {
            if(root->left->val <= leftLimit) return false;
            if(root->val <= root->left->val) return false;

            left = _isValidBST(root->left, leftLimit, root->val);
        }

        if(root->right)
        {
            if(root->right->val >= rightLimit) return false;
            if(root->val >= root->right->val) return false;

            right = _isValidBST(root->right, root->val, rightLimit);
        }

        return left && right;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    TreeNode* prev=NULL;
    bool isValidBST(TreeNode* root) {
        if(!root)
            return true;
       if(!isValidBST(root->left))
          return false;
       if(prev && root->val <=prev->val)
           return false;
        prev=root;
        return isValidBST(root->right);
    }
};