Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 관계형 모델
- baekjoon
- Application Layer
- 프로그래머스
- BHS
- 문제풀이
- 데이터베이스
- 임베디드
- BST
- STL
- ps
- Database
- 릿코드
- DB
- 자료구조
- Djikstra
- 백준
- Transport layer
- 다익스트라
- Embedded
- 응용 계층
- Network
- 부트시퀀스
- dp
- C++
- 네트워크
- leetcode
- 전송 계층
- swea
- boot sequence
Archives
- Today
- Total
BOBO's Note
[ LeetCode ] 98. Validate Binary Search Tree 본문
https://leetcode.com/problems/validate-binary-search-tree/
풀이 방법
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);
전체 코드는 여기서 확인할 수 있다.
'Algorithm > Problem Solving' 카테고리의 다른 글
[ LeetCode ] 53. Maximum Subarray (0) | 2020.07.04 |
---|---|
[ 프로그래머스 ] 큰 수 만들기 (0) | 2020.06.30 |
[ 프로그래머스 ] N으로 표현 (0) | 2020.06.26 |
[ LeetCode ] 480. Sliding Window Median (0) | 2020.06.24 |
[ Baekjoon ] 2110. 공유기 설치 (0) | 2020.06.24 |
Comments