LeetCode: 99번 (Recover Binary Search Tree) [JAVA]

문제 링크

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

Recover Binary Search Tree - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 노드들을 저장할 ArrayList, 노드들의 값을 저장할 ArrayList를 각각 선언 후 초기화
2. 주어진 트리를 중위 순회하며, 해당 노드 순서일 때 해당 노드와 값을 각각의 ArrayList에 추가
3. 중위 순회 후 전체 트리 속 노드 값들을 추가한 ArrayList를 오름차순 정렬
4. 이후 노드들을 저장한 ArrayList를 for문을 통해 돌며, 해당 노드에 노드 값을 저장한 ArrayList에서 동일한 순서의 노드 값을 가져와 삽입

 이진 탐색 트리의 경우, 중위 순회를 하면 오름차순 형태로 수들이 정렬되는 특징을 가지고 있기에 이를 활용하여 문제를 풀 수 있다. 우선 트리의 노드들을 저장할 ArrayList(nodes), 그리고 노드의 값들을 저장할 ArrayList(nodeValues)를 선언하고 초기화한다. 이후 주어진 트리에 대해 중위 순회를 진행하며, 해당 노드 순서일 때 해당 노드와 노드 속 값을 각각 nodes와 nodeValues에 추가한다.
 그렇게 중위 순회를 마친 후엔, 노드 속 값들만 모여 있는 nodeValues를 오름차순으로 정렬한다. 오름차순 정렬 후의 결과 형태가 옳게 구성된 이진 탐색 트리 속 노드들의 값들이기 때문에, 이를 이제 nodes 속 노드들에 순차대로 대입해준다. for문을 통해 nodes를 돌며, 특정 순서 속 노드에 nodeValues 속 동일한 순서의 값을 가져와 삽입하면 된다.

 

class Solution {
    ArrayList<TreeNode> nodes = new ArrayList<>();
    ArrayList<Integer> nodeValues = new ArrayList<>();

    public void recoverTree(TreeNode root) {
        inorderTraversal(root);//중위 순회
        Collections.sort(nodeValues);//전체 트리 속 값들을 오름차순 정렬

        for (int i = 0; i < nodes.size(); i++) {//노드를 돌며 올바른 값을 삽입
            nodes.get(i).val = nodeValues.get(i);
        }
    }

    void inorderTraversal(TreeNode node){//중위순회
        if (node == null) {
            return;
        }

        inorderTraversal(node.left);
        nodes.add(node);//중위 순회를 돌며 해당 노드를 ArrayList에 삽입
        nodeValues.add(node.val);//해당 값 또한 따로 삽입
        inorderTraversal(node.right);
    }
}

결과