Hacktoberfest/validate_binary_search_tree.cpp at main · Summer2123/Hacktoberfest · GitHub

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
// https://leetcode.com/problems/validate-binary-search-tree/

struct Resolver {
    long minVal, maxVal;
    bool result;
};

class Solution {
public:
    Resolver helper(TreeNode* root) {
        if(!root) return {LONG_MIN, LONG_MAX, true};

        Resolver left = helper(root->left);
        if(!left.result) return left;

        bool leftMinCheck=true, leftMaxCheck=true;
        if(left.minVal==LONG_MIN) {
            leftMinCheck=false;
            left.minVal=root->val;
        }
        if(left.maxVal==LONG_MAX) {
            left.maxVal=root->val;
            leftMaxCheck=false;
        }

        if((leftMinCheck && left.minVal >= root->val) || (left.maxVal >= root->val && leftMaxCheck)) return {1, 1, false};

        Resolver right = helper(root->right);
        if(!right.result) return right;

        bool rightMinCheck = true, rightMaxCheck=true;
         if(right.minVal==LONG_MIN) {
            rightMinCheck=false;
            right.minVal=root->val;
        }
        if(right.maxVal==LONG_MAX) {
            right.maxVal=root->val;
            rightMaxCheck=false;
        }

        if( (rightMaxCheck && right.maxVal <= root->val) || (rightMinCheck && right.minVal <=root->val)) return {1, 1, false};

        return {left.minVal, right.maxVal, true};
    }

    bool isValidBST(TreeNode* root) {
        return helper(root).result;
    }
};