[LeetCode] 99 | Recover Binary Search Tree | Python

---

문제 링크: https://leetcode.com/problems/recover-binary-search-tree/

---

문제

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.

---

조건

• The number of nodes in the tree is in the range [2, 1000].
• $-2^{31}$ <= Node.val <= $2^{31}$ - 1

---

내 풀이

BST는 iterative로 푸는 것이 편하다.

모든 노드를 돌아다니며 BST의 특성에 맞게 잘 되어있는지 확인하고, 특성에 맞지 않는 것이 있다면 그 노드를 저장한다.

문제에서 특성에 맞지 않는 노드는 무조건 두 개라고 했으니 두 개가 나온다면 그 val을 서로 바꾸면 된다.

---

코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.prev = TreeNode(-float('inf'))
        self.change1, self.change2 = None, None
        
        self.get2nodes(root)
        
        self.change1.val, self.change2.val = self.change2.val, self.change1.val
        
    def get2nodes(self, root):
        if root:
            self.get2nodes(root.left)
            
            if self.prev.val > root.val:
                if not self.change1:
                    self.change1 = self.prev
                self.change2 = root
                
            self.prev = root
        
            self.get2nodes(root.right)