99. Recover Binary Search Tree

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

Recover Binary Search Tree - LeetCode

 

이진 트리가 주어졌을 때, 순서가 잘못 들어간 두 개의 노드를 찾아 원래의 모습으로 복구하는 문제다.

나는 처음에 root부터 양쪽 leaf로 검사 해나가는 방법을 썼는데, 정답을 찾아보니 최소값(left->left...)부터 최대값(right->right...)까지 순차적으로 비교하며 찾는게 정답이였다.... 어렵다.. 다들 왜이렇게 똑똑할까

 

단 두 개의 노드만 바뀌었다고 하니 first와 second 변수를 뒀지만 만약 여러 개의 노드가 바뀌었다면 최초 생각대로 vector로 비교하면서 했을것같다.

 

1. 트리 상에서 정상임을 판단하기 위해 임시 최소값 변수(parent_)를 범위의 최소 값으로 설정한다.

2. 일단 tree를 타며 최소 값을 찾는다.

(left->left...->left) 부터 시작해 순차적인 값을 방문한다.

3. 임시 최소값 변수(parent_)와 tree 값을 비교하며 현재 방문한 노드의 값이 정상인지 판별한다.

4. 비정상이면 swap할 변수에 저장한다.

(바뀔 Node들은 이전에 기록된 parent_와 현재 방문한 Node다)

5. 정상이면 parent_를 갱신한다.

6. 모든 노드를 방문했다면 swap 후 종료

/**
 * 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 {
public:
    void swap(TreeNode* l, TreeNode* r)
    {
        if (!l || !r) {
            return;
        }
        
        int val = l->val;
        l->val = r->val;
        r->val = val;
    }
    void solve(TreeNode* node)
    {
        if (!node) {
            return;
        }
        
        // 제일 낮은 값의 node로 이동
        solve(node->left);
        
        if (parent_->val >= node->val)
        {
            first_ = parent_;
            second_ = node;
        }
        else
        {
            // left tree가 다 돌았으면 parent(최소값) 갱신
            parent_ = node;
        }
        
        solve(node->right);
    }
    void recoverTree(TreeNode* root) {
        first_ = nullptr;
        second_ = nullptr;
        // 가장 작은 값부터 배열로 node부터 탐색
        parent_ = new TreeNode(INT_MIN);
        solve(root);
        swap(first_, second_);
    }
private:
    TreeNode* first_;
    TreeNode* second_;
    TreeNode* parent_;
};