[leetCode] 98. Validate Binary Search Tree

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

Validate Binary Search Tree - LeetCode

 

해당 문제의 조건은 이진트리에서 왼쪽 서브트리는 해당 노드의 값보다 더 작은 값을 가지는 노드가 존재해야 하고, 오른쪽 서브트리는 무조건 더 커야한다.

 

루트 노트 기준으로 왼쪽은 루트보다 더 작아야 하며, 오른쪽은 모든 노드들의 값이 더 커야한다.

/**
 * 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) 
    {
        return Search(root, LLONG_MIN, LLONG_MAX);   
    }

    bool Search(TreeNode* node, long long min, long long max)
    {        
        if(node == nullptr)
            return true;

        if(node->val <= min)
            return false;

        if(node->val >= max)
            return false;

        return Search(node->left, min, node->val) && Search(node->right, node->val, max);
    }

};