[leetcode] Recover Binary Search Tree

실수

문제 조건 파악 실패 : 문제에 2개의 노드가 잘못 배치되어있다고 써있다

올바른 이진 트리의 의미

이진트리가 맞는지 아닌지 확인할때, 루트의 왼쪽 자식 , 오른쪽 자식만 고려하면 안된다.

예를 들어 10 6 20 NULL NULL 5 23 의 경우에는 루트의 왼쪽 자식 오른쪽 자식만 고려했을 경우 맞는 케이스가 된다.

10의 자식이 6과 20 인 경우 → true

20의 자식이 5와 23 인 경우 → true

결과 → true

유의할점

문제에 2개의 노드가 잘못 배치되어있다고 써있다 → 2개의 노드를 찾아서 swap하면 된다.

정렬된 순서에서 잘못된 두개의 노드는 다음과 같은 특징을 가진다.

• 첫번째 잘못된 노드는 그 다음 순서의 노드보다 크다. → 이전 노드가 현재 노드보다 크면 첫번째 잘못된 노드이다.
• 두번째 잘못된 노드는 그 이전 순서의 노드보다 작다.

이는 큰값이 앞으로 , 작은 값이 뒤로 갔기 때문에 생기는 현상이다.

→ 최악의 경우 2개의 노드를 찾는데 N번 걸린다. N번의 recursion은 O(N)의 공간 복잡도를 요구한다. 추가 문제 만족하지 않는다. (추가 문제 : O(1)의 시간에 해결 하기)

추가 문제 → Morris Traversal 이용.

풀이

전위 순회로 트리의 값을 추출해서 vector에 담은 뒤에 해당 값을 정렬한다.

그 후 그 값들을 다시 전위 순회하면서 삽입한다.

inorder의 기본 코드

private void traverse (TreeNode root) {
   if (root == null)
      return;
   traverse(root.left);
   // Do some business
   traverse(root.right);
}

코드

C++ : 내가 짠거 , inorder 두번 → 같은 일을 두번함. 효율적이지 않음

/**
 * 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 {
private:
    vector <int> _arr;
public:
    void inorder(TreeNode* root){
        if(root==NULL) return;
        inorder(root->left);
        _arr.push_back(root->val);
        inorder(root->right);
    }
    
    void recover(TreeNode* root,int&idx){
        if(root==NULL) return;
        recover(root->left,idx);
        root->val = _arr[idx++];
        recover(root->right,idx);
    }
    
    void recoverTree(TreeNode* root) {
        inorder(root);
        sort(_arr.begin(),_arr.end());
        int idx = 0;
        recover(root,idx);
    }
};

C++ : inorder 한번

//작성예정