98. Validate Binary Search Tree | LeetCode 문제 풀이

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

Validate Binary Search Tree - LeetCode

 

문제

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

 

-> 해당 이진 트리가 유효한지 확인한 후 결과를 true/false로 반환하는 문제였다.

 

예제

 

Example 1:

Input: root = [2,1,3]
Output: true

Example 2:

Input: root = [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.

 

 

 

---

 

풀이

 

1. 처음 짰던 코드 (틀림 주의!)

 

 

처음에 다음과 같은 생각으로 코드를 짜보았다.

수업시간에 배운 재귀함수를 최대한 이용하려고 하였다.

 

문제 접근

 

풀이 코드

/**
 * 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) {
        if (root == nullptr) return true;

        if (root->left && (root->left->val > root->val)) return false;
        if (root->right && (root->right->val < root->val)) return false;

        return isValidBST(root->left) && isValidBST(root->right);
    }
};

 

결과는!?!?!?!??

 

 

틀렸다~~~ 72개의 test case는 통과했지만 남은 test case는 통과하지 못 했다.

통과하지 못 한 예제의 input data를 보자마자 내가 고려하지 못 한 부분이 어디인지 바로 알 수 있었다.

 

위 그림에서 알 수 있듯이 node의 limit 상황을 제대로 고려했어야 한다.

 

 

 

 

2. 정답 코드

 

해결을 위해 많이 생각해보았지만 리트 코드를 이용해 처음 풀어보는 문제이기도 하고 재귀 함수에 익숙하지 않아

https://m42-orion.tistory.com/38 블로그를 참고하였다.

 

참고한 후 다시 코드 설정을 해보았다.

우선 먼저, 재귀함수의 매개변수 설정을 다시 하였다.

해당 값의 min과 max를 두어 범위를 다시 설정하였다.

 

가장 중요한 부분은 다음과 같았다.

 

• root->left의 min: root의 min
• root->left의 max: root
• root->right의 min: root
• root->right의 max: root의 max

현재 노드의 root 노드와의 대소비교뿐만 아니라 root의 min 또는 max 까지 고려해주어야 정확히 부합하는 이진 트리를 판별할 수 있다.

 

그리고 학교 수업시간에서 배웠듯이 함수 오버로딩을 통해 문제에서 필요로 하는 함수를 재설정하여 사용하는 것도 매우 좋은 방법인 것 같다.

 

/**
 * 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, TreeNode* min, TreeNode* max) {
        if (root == nullptr) return true;

        if (min && (min->val >= root->val)) return false; // 앞에 min && 를 해주는 이유는 min의 범위가 null일 경우 비교의 필요가 없기 때문에 상황을 제외시키기 위함이다
        if (max && (max->val <= root->val)) return false;

        return isValidBST(root->left, min, root) && isValidBST(root->right, root, max);

    }
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, nullptr, nullptr);
    }
};