Today's Challenge

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

Recover Binary Search Tree - LeetCode

음.. 이번 문제는 이해부터가 좀 어려운 듯?
그런데 매우 간단한 방법을 사용한 풀이가 있다. 재귀도 안쓰고.

공책에 Example에 대한 로직을 쭉 따라가봤는데 신기하게도 first와 second가 제대로 구해진다.

1. first는 root와 pre를 비교해서 딱 한 번만 구한다. BST 구조에 맞지 않는 값을 구하는 로직으로 보면 될 거 같다.
2. second는 first 값이 존재할 때, root와 pre를 비교해서 구한다. 이 작업은 여러 번 이루어질 수 있다.

작성한 소스는 다음과 같다.

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        s = []
        pre, first, second = None, None, None
        
        while root or len(s) > 0:
            while root is not None:
                s.append(root)
                root = root.left
            
            if len(s) > 0:
                root = s.pop()
                
                if first is None and pre and pre.val > root.val:
                    first = pre
                
                if first and pre.val > root.val:
                    second = root
                    
                pre = root                
                root = root.right
            
        first.val, second.val = second.val, first.val