[99클럽 코테 스터디] 18일차 TIL - Increasing Order Search Tree

Hoxy?·2024년 8월 8일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99클럽 코테 스터디

목록 보기

18/42

오늘의 학습 키워드

</> 깊이/너비 우선 탐색(DFS/BFS)

공부한 내용 본인의 언어로 정리하기

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode newRoot = null; // 새로운 트리의 루트 노드
    private TreeNode current = null; // 새 트리에서 마지막으로 추가된 노드

    public TreeNode increasingBST(TreeNode root) {
        return sort(root); // 트리를 재귀적으로 정렬하여 새로운 트리를 생성
    }

    private TreeNode sort(TreeNode node) {
        if (node == null) {
            return null; // 현재 노드가 null이면 null 반환
        }
        
        // 왼쪽 서브트리를 재귀적으로 정렬
        TreeNode leftSubtree = sort(node.left); 

        // 현재 노드를 새로운 트리에 추가
        if (current == null) {
            // 새로운 트리의 루트 노드를 생성
            newRoot = new TreeNode(node.val); 
            current = newRoot; // 현재 노드를 새 루트로 설정
        } else {
            // 현재 노드의 오른쪽에 새 노드를 추가
            current.right = new TreeNode(node.val); 
            current = current.right; // 현재 노드를 새로 추가된 노드로 업데이트
        }

        // 오른쪽 서브트리를 재귀적으로 정렬
        sort(node.right); 

        return newRoot; // 새로운 트리의 루트 노드를 반환
    }
}

오늘의 회고

오늘은 이진 탐색 트리를 재구성하는 문제를 통해 깊이 우선 탐색(DFS)의 한 형태인 중위 순회에 대해 학습했습니다. 처음에는 이해가 가지 않아서 대략 1시간 넘게 계속 검색만 하면서 알아봤던 것 같습니다. 어제는 int 배열로 만들었다면 오늘은 트리를 만들어야 했고 처음 만들어 보는 것이었기 때문에 더 어려웠습니다.

우선 재귀 호출을 이용한 sort 메서드로 중위 순회를 하였습니다. 하지만 어제와 다른 점은 값을 배열이 아닌 트리에 추가를 해야한다는점 그리고 오른쪽으로 추가를 해서 정렬을 해야한다는 점이었습니다.
그래서 현재 노드와 새로운 트리를 만들어서 시작을 하였고 중위 순회를 시작해 왼쪽 서브트리를 처리하고 현재 노드를 새로운 트리에 추가를 하고 오른쪽 서브트리를 처리하는 순서로 똑같이 진행 하였습니다.
여기서 또 차이점이 현재 노드를 새로운 트리가 추가할 때 현재 노드가 없으면 바로 새로운 트리에 추가하여 현재 노드를 새 노드로 설정하고 아닐 경우 현재 노드의 오른쪽에 새 노드를 추가하여 현재 노드를 오른쪽에 추가한 노드는 현재 노드로 업데이트 시켜 주었습니다.

처음에는 트리의 구조를 변경하는 과정이 복잡하게 느껴졌지만, 재귀 호출의 특성을 이해하면서 점차 이해가 갔습니다. 특히, 새로운 트리를 구성하는 과정에서 newRoot와 current 변수를 만들어 트리의 구조를 효과적으로 관리하는 방법을 배웠습니다. 이 방식은 원본 트리의 구조를 변경하지 않고 새로운 트리를 만들어 반환한다는 점에서 매우 유용했습니다.
다만, 매우 큰 트리의 경우 스택 오버플로우의 위험이 있다는 점도 인식하게 되었습니다.

AI 코드리뷰

현재 코드의 장점

재귀를 사용한 간결하고 직관적인 구현
원본 트리를 변경하지 않고 새로운 트리를 생성
중위 순회를 통해 BST의 특성을 잘 활용함

현재 코드의 단점

매우 깊은 트리의 경우 스택 오버플로우 가능성 존재
새로운 노드를 계속 생성하므로 메모리 사용량이 증가할 수 있음

시간 복잡도

시간 복잡도: O(n), 여기서 n은 트리의 노드 수
공간 복잡도: O(n), 새로운 트리를 생성하기 때문

개선된 코드 제안

class Solution {
    public TreeNode increasingBST(TreeNode root) {
        return increasingBST(root, null);
    }

    private TreeNode increasingBST(TreeNode root, TreeNode tail) {
        if (root == null) return tail;
        TreeNode res = increasingBST(root.left, root);
        root.left = null;
        root.right = increasingBST(root.right, tail);
        return res;
    }
}

개선된 버전의 장점: