98. Validate Binary Search Tree [Medium]

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

Validate Binary Search Tree - LeetCode

 

이진 트리의 Root가 주어졌을 때, 해당 트리가 유효한 이진 검색 트리 인지(BST) 검증하는 문제다.

유효한 이진 트리는 다음과 같다.

 

1. Node의 왼쪽 하위 트리에는 노드의 Key보다 작은 Key만 존재해야 한다.

2. Node의 오른쪽 하위 트리에는 노드의 Key보다 큰 Key만 존재해야 한다.

3. 왼쪽과 오른쪽 하위 트리도 모두 이진 검색 트리여야 한다.

 

source

/**  * 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 checkValidBST(TreeNode* node, TreeNode* min, TreeNode* max) {         if (nullptr == node) {             return true;         }         if ((min && node->val <= min->val) || (max && node->val >= max->val)) {             return false;         }         return checkValidBST(node->left, min, node) && checkValidBST(node->right, node, max);     }     bool isValidBST(TreeNode* root) {         if (nullptr == root) {             return true;         }         return checkValidBST(root->left, nullptr, root) && checkValidBST(root->right, root, nullptr);     } };

<실행 결과>

 

혼자서 하다가 다른 사람의 풀이를 봤다.

처음엔 root 기준으로 직전 노드의 값만 넘겨서 좌/우를 비교하게 했으나, 돌려보니 FAIL이 떴다.

생각해보니 앞앞단에서 5가 나왔는데 오른쪽 트리 밑밑에서 4가 왼쪽에 나와버리면 이진 탐색 트리가 아닌걸 깨달았다.

결국 트리별로 최소값이 필요하다는 생각이 들었다.

각 방향마다 최대와 최소를 같이 주고, 하위 트리를 체크하는 식으로 하는 방법으로 풀면 되겠다.