Leetcode 99. 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.

• 이진 검색 트리의 root가 주어진다.
  두개의 노드 값이 실수로 바뀌었을때
  In-place 로 바뀐 부분을 다시 돌려 놓아라

EX. 1과 3이 바뀌었다, 둘을 바꿔준다.

제한

• 트리 내 노드의 갯수는 2~1000 개이다.
• 노드의 값은 32비트 정수 범위 안이다.

풀이

1. 먼저 주어진 Binary Search Tree의 값을 inorder로 순회하여 저장한다.
   • 정상적인 Binary search Tree 의 경우 반드시 inorder으로 순회하면 값이 오름차순이 된다!.
2. 그 후 주어진 배열을 오름차순으로 정렬한다.
   • 그럼 틀어져서 오름차순이 아닌 배열과 원래 BST의 오름차순 배열 두개가 생긴다.
3. 두 배열을 비교해 틀린 부분에 해당하는 두 숫자의 노드를 바꿔준다.
   • 그러면 다시 올바른 BST로 변경된다!

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        self.temp = []

        def dfs(node: TreeNode):
            if not node: return

            dfs(node.left)
            self.temp.append(node)
            dfs(node.right)
		
        // inorder traversal으로 틀어진 부분을 찾는다.
        dfs(root)

        srt = sorted(n.val for n in self.temp)
        tempdata = [n.val for n in self.temp]

        a, b = 0, 0
        for x, y in zip(srt, tempdata):
            if x != y:
                a, b = x, y
                break
		// 다른 부분을 찾아

		// 다시 바꿔준다.
        def revice(a: int, b: int, node: TreeNode):
            if not node:
                return
            if node.val == a:
                node.val = b
            elif node.val == b:
                node.val = a
            revice(a, b, node.left)
            revice(a, b, node.right)

        revice(a, b, root)

포인트!

• Binary Search Tree는 Inorder Traversal 시 반드시 오름차순이 된다!!!