[ LeetCode ] 98. Validate Binary Search Tree

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

Validate Binary Search Tree - LeetCode

풀이 방법

Binary Search Tree는 모든 노드가 다음을 만족하는 이진트리이다.

모든 왼쪽 서브트리의 자식 노드 값 <= 노드 값 < 모든 오른쪽 서브트리의 자식 노드 값

즉, 노드 값이 왼쪽 서브트리의 노드 중 최대값보다 크거나 같고 오른쪽 서브트리의 노드 중 최소값보다는 작아야 한다. 이를 만족하지 않으면 BST가 아니다. 

if(max != nullptr && root->val >= max->val) return false;
if(min != nullptr && root->val <= min->val) return false;

 

모든 노드에 대해 이 조건을 만족해야 하므로 각 서브트리에 대해 recursive하게 확인한다.

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

 

전체 코드는 여기서 확인할 수 있다.