짱아의 개발 기록장

LeetCode : 99. Recover Binary Search Tree 본문

Algorithm/LeetCode

LeetCode : 99. Recover Binary Search Tree

jungahshin 2020. 12. 30. 13:21
반응형

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

 

참고 유투브 링크

www.youtube.com/watch?v=LR3K5XAWV5k

반응형
Comments