leetcode : Recover Binary Search Tree

Recover Binary Search Tree - LeetCode

Recover Binary Search Tree - LeetCode

 

BST니까 inorder traversal하면 기본적으로 오름차순된 숫자가 나열될것이다.

그 중 두 개가 서로 위치가 바뀌었다는거니까 순회하다보면 오름차순으로 가다가 갑자기 숫자가 뚝 떨어지는 부분이 있을것이다. 인접한 두 값의 노드의 자리가 바뀐거라면 뚝 떨어지는 구간이 한 번 나올 것이고 멀리 떨어진 두 값의 노드가 바뀐거라면 뚝 떨어지는 구간이 두 번 나올것이다.

 

# 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.
        """
        
        prev = TreeNode(val = -2**31)
        swap = [] # 뚝 떨어지는 노드들 저장
        stack = []
        
        while True:
            while root:
                stack.append(root)
                root = root.left
            if not stack:
                break
                
            node = stack.pop()
            
            if node.val < prev.val:
                swap.append((prev, node))

            prev = node
            
            if node.right:
                root = node.right
        
        if len(swap) == 1:
            swap[0][0].val, swap[0][1].val = swap[0][1].val, swap[0][0].val
            
        if len(swap) == 2:
            swap[0][0].val, swap[1][1].val = swap[1][1].val, swap[0][0].val

 

시간복잡도는 O(N)이고 공간복잡도는 O(1)이다. (사실 DFS를 하기 때문에 정확히는 공간복잡도 O(logN)이지만 그건 안치는거니까 무시..)