99. Recover Binary Search Tree | LeetCode 문제 풀이

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

Recover Binary Search Tree - LeetCode

 

문제

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

 

 

-> 이진 트리가 성질에 맞지 않을 경우 이진 트리의 생김새(구조) 자체는 변경하지 않으면서, 해당 값들만 swap하여 성질에 맞는 이진 트리로 변경하는 코드를 짜야한다.

 

예제

 

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

 

 

 

 

---

 

 

 

 

풀이

 

1. 처음 짰던 코드 (틀림 주의!)

/**
 * 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 recoverTree(TreeNode* root, TreeNode* min, TreeNode* max) {
        if (root == nullptr) return;

        if (min && (min->val >= root->val)) {
            int temp;
            temp = min->val;
            min->val = root->val;
            root->val = temp;
        }
        if (max && (max->val <= root->val)) {
            int temp;
            temp = max->val;
            max->val = root->val;
            root->val = temp;
        }

        recoverTree(root->left, min, root);
        recoverTree(root->right, root, max);
    }

    void recoverTree(TreeNode* root) {
        recoverTree(root, nullptr, nullptr);
    }
};

 

 

 

98번 문제를 푼 후 99번 문제에 접근했다보니,

98번의 발상을 그대로 99번의 문제에 적용하여 트리가 조건에 맞지 않으면 해당 값들을 swap해주면 될 것이라고 생각했다.

 

• 참고 | 98번 : https://chaesoong2.tistory.com/6

 

근데!

 

 

단순히 값들만 비교한 후 swap을 하기에는 고려해야할 사항이 많다는 사실을 모르고 있었다.

 

2, 3, 1의 경우)

내가 짠 코드에 의하면

먼저, 2와 3이 swap되어 3, 2, 1이 되고

그 후, 3과 1이 swap되어 1, 2, 3이 된다.

 

이를 트리 형식으로 표시해보면

 

        1

2              3

 

다음과 같이 표현할 수 있는데 left의 key 값이 root의 key 값보다 크므로 이는 이진 탐색 트리의 성질에 어긋나는 트리라고 볼 수 있다.

 

 

 

... 머리가 더이상 안 돌아간다

꼭 내 힘으로 풀어보고 싶은데 당장은 잘 모르겠어서...

나중에 다시 풀어본 후 풀이 수정하도록 하겠다...