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 | 31 |
Tags
- 스마일게이트
- 백준
- 1편
- 식단
- 중반부
- Union-find
- 보석쇼핑
- 삼성 #코테 #2020상반기 #c++
- 알고리즘
- Algorithm
- LIS #Algorithm #요소추적
- 카카오인턴
- 소감
- c++
- Smilegate
- BFS
- 코테
- 투포인터
- 코딩테스트
- 서버개발캠프
- 카카오
- BaekJoon
- 유니온파인드
- IBK기업은행 #기업은행 #디지털 #직무 #정리
Archives
- Today
- Total
짱아의 개발 기록장
LeetCode : 99. Recover Binary Search Tree 본문
반응형
dfs중에서도 hard난이도에 해당되는 문제이다.
Tree문제인데, BST의 두 노드가 바뀐 상태로 입력이 주어져질 때, structure을 바꾸지 않고 recovery하면 된다.
솔직히 InorderTraversal 후 모든 두 개의 값을 reverse해주고 오름차순으로 정렬되는 지 BruteForce로 일일히 확인하는 그런 방법 밖에 생각이 나지 않아서.... 다른 외국 유투버의 풀이방법을 참고했다.
간단한 로직은 다음 사진으로 첨부했다.
사진 그대로
1) 역전되는 곳이 1pair 생긴다면, 첫 번째 값을 first로, 두 번째 값을 second로 간주했다.
2) 역전되는 곳이 2pair 생긴다면, 첫 번째 pair의 첫 번째 값을 first로, 두 번째 pair의 두 번째 값을 second로 간주했다.
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
class Solution {
public:
vector<int> val;
int first, second;
void InorderTraversal(TreeNode* root){
if(root==NULL){
return;
}
InorderTraversal(root->left);
val.push_back(root->val);
InorderTraversal(root->right);
}
void changeValTree(TreeNode *root){
if(root==NULL){
return;
}
changeValTree(root->left);
if((root->val)==first){
(root->val) = second;
}else if((root->val)==second){
(root->val) = first;
}
changeValTree(root->right);
}
void recoverTree(TreeNode* root) {
// Inorder Traversal로 먼저 vector에 값 넣어주고
// 하나씩 탐색하면서 역전되는 곳 찾기
// 역전되는 곳 1pair -> 첫 번째 값이 first, 두번째 값이 second
// 역전되는 곳 2pair -> 첫 번째 pair의 첫 번째 값이 first, 두 번째 pair의 두 번째 값이 second
InorderTraversal(root);
int prev = val[0];
first = NULL, second = NULL;
for(int i=1; i<val.size(); i++){
if(prev>val[i] && first==NULL){
first = prev;
}
if(prev>val[i] && first!=NULL){
second = val[i];
}
prev = val[i];
}
changeValTree(root);
}
};
|
cs |
참고 유투브 링크
반응형
'Algorithm > LeetCode' 카테고리의 다른 글
LeetCode : 101. Symmetric Tree (0) | 2021.01.01 |
---|---|
LeetCode : 100. Same Tree (0) | 2020.12.31 |
LeetCode : 98. Validate Binary Search Tree (0) | 2020.12.29 |
LeedCode : 17. Letter Combinations of a Phone Number (0) | 2020.12.29 |
LeetCode : 11. Container With Most Water (0) | 2020.12.28 |