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.
Example 1:
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
Example 2:
Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.
Constraints:
- The number of nodes in the tree is in the range
[2, 1000]. 231 <= Node.val <= 231 - 1
두 개의 노드가 잘못적힌 BST 를 원상복귀 시키는 문제이다. 첫번째 예제를 리스트로 정렬하면 [3, 2, 1] 이 된다. 정상적인 BST 였다면 [1, 2, 3] 이 되었어야 한다. 따라서 정상적인 BST 로 만들기 위해 3 과 1 의 값을 바꾸면 회복(recover) 된다.
두번째 예제도 마찬가지로 리스트로 정렬하면 [1, 3, 2, 4] 가 된다. 정상적인 BST 였다면 [1, 2, 3, 4] 가 되었어야 한다. 따라서 정상적인 BST 로 만들기 위해 3 과 2 의 값을 바꾸면 회복된다.
즉, 잘못된 BST 를 리스트로 변경했을 때 val 의 값이 오름차순으로 변경되면 올바른 BST 로 회복된다. 따라서 오름차순으로 변경하기 위해 root 로 받은 BST 를 리스트에 담고, 정렬 후 두 리스트를 비교하였다. (트리의 형태를 유지하기 위해 노드의 값만을 변경한다.)
- root 의 노드들을 담은 리스트를 생성한다.
- 노드의 val 값을 기준으로 오름차순 정렬한 새로운 리스트를 생성한다.
- 두 리스트를 비교하여 값이 다를 경우 바꾸어 준다.
Code
# 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.
"""
nodes = []
def inorder(node: Optional[TreeNode]):
if node is None:
return
inorder(node.left)
nodes.append(node)
inorder(node.right)
inorder(root)
sortedNodes = sorted(nodes, key=lambda x: x.val)
for i in range(len(nodes)):
if nodes[i] != sortedNodes[i]:
nodes[i].val, sortedNodes[i].val = sortedNodes[i].val, nodes[i].val
breaknodes 와 sortedNodes 둘 다 노드 객체를 그대로 가지고 있으므로 한 쪽의 리스트에서 val 을 변경하면 다른 리스트의 노드의 값도 변경된다. 따라서 ‘두개’ 의 노드만 다르다는 것을 이용하여 각자의 값을 변경하고 반복을 종료한다.
