리트코드 Recover Binary Search Tree 코드 및 해설 (파이썬)

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

Recover Binary Search Tree - LeetCode

 

올바른 BST라면 inorder 순회를 했을 때 값들이 오름차순으로 정렬되어야 한다는 사실을 이용해 풀이했습니다. inorder 순회를 하면서 result에 값을 저장하고, 오름차순 정렬이 되지 않는 부분들의 노드를 발견하면 swap에 추가적으로 저장했습니다. 순회가 끝난 후 swap의 첫 노드와 마지막 노드의 값을 서로 교환했습니다.

 

https://codlingual.tistory.com/173?category=868745 

백준 트리 순회 코드 및 해설 (파이썬)

 

# 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: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        result, swap = self.inorder(root, result=[], swap=[])
        # swap의 첫 번째 값과 마지막 값을 서로 교환 
        swap[0].val, swap[-1].val = swap[-1].val, swap[0].val

    
    # inorder traversal
    def inorder(self, root, result, swap):
        node = root
        if node:
            # 왼쪽 자식
            if node.left:
                result, swap = self.inorder(node.left, result, swap)
            # 대소관계 맞지 않으면 swap에 저장 
            if result and result[-1].val >= node.val:
                swap += [result[-1], node]
            # 루트
            result.append(node)
            # 오른쪽 자식 
            if node.right:
                result, swap = self.inorder(node.right, result, swap)
        return result, swap