[99클럽 코테 스터디] 18일차 TIL DFS/BFS

 

 

오늘의 문제는 LeetCode

 

Increasing Order Search Tree

 

 

문제

 

 

 

문제 설명 

 

이진 탐색 트리가 주어지면 모든 노드를 크기 순서대로 정렬해야 합니다. 대신 모든 노드는 왼쪽 자식 노드가 없고 오른쪽 자식 노드만 가져야 합니다. 

 

예시 입력값 : 

root = [5,3,6,2,4,null,8,1,null,null,null,7,9]

 

출력값 : 

[1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 

 

 

문제 풀이 시간 

권장 풀이 시간은 60분이었고, 저는 41분이 걸렸습니다.

 

 

 

문제 접근 방식

먼저 DFS 알고리즘을 이용해 트리의 모든 값을 정렬된 순서로 리스트에 저장합니다. 

그 다음 저장된 값을 이용해 새로운 트리를 만듭니다. 새로운 트리의 노드는 오른쪽 자식만 갖도록 합니다. 이를 위해 트리의 시작점을 설정하고 이후 모든 노드를 오른쪽 자식에 연결합니다. 

 

 

 

문제 풀이

import java.util.ArrayList;


/**
 * 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 {
    public TreeNode increasingBST(TreeNode root) {
        List<Integer> inOrderList = new ArrayList<>();  

        inOrder(root, inOrderList);

        TreeNode tempNode = new TreeNode(0);
        TreeNode currnetNode = tempNode; 
        
        for(int val : inOrderList) {
            currnetNode.right = new TreeNode(val);
            currnetNode = currnetNode.right;
        }

        return tempNode.right;
    }

    public void inOrder(TreeNode node, List<Integer> inOrderList) {
        if(node != null) {
            inOrder(node.left, inOrderList);
            inOrderList.add(node.val);
            inOrder(node.right, inOrderList);
        }
    }
}

 

 

중위 순회를 통한 오름차순 정렬하기 

이진 탐색 트리의 특성을 살펴보면 왼쪽 자식 노드는 부모 노드 보다 작고, 오른쪽 자식 노드는 부모 노드보다 큽니다. 따라서 왼쪽 자식, 부모 노드, 오른쪽 자식 순으로 노드를 방문하는 중위 순회를 하면 오름차순으로 순회를 할 수 있습니다. 이를 리스트에 저장하면 트리의 모든 노드가 오름차순으로 정렬되어 저장되게 됩니다. 

반대로 오른쪽 자식, 부모 노드, 왼쪽 자식 순으로 노드를 방문하면 내림차순으로 순회하게 됩니다. 

 

 

 

오른쪽 자식 노드만 갖는 새로운 트리 생성하기

어제의 풀이와 달라진 점은 중위 순회 한 결과를 그대로 반환 하는 것이 아닌, 오른쪽 자식만 가진 트리를 결과로 반환해야 하기 때문에 중위 순회 결과를 새로운 트리를 만들어 저장해야 한다는 것입니다. 

 

먼저 새로운 트리를 만들기 위해 새로운 트리의 시작점을 생성합니다. 그리고 현재 노드를 가리키는 포인터를 선언합니다. 

TreeNode tempNode = new TreeNode(0);
TreeNode currnetNode = tempNode;

 

다음으로 중위 순회한 결과를 for-each 문을 사용해 리스트를 순환합니다.

현재 노드의 오른쪽 자식으로 새로운 노드를 생성해 연결합니다. 그 후 현재 노드를 새로 만든 노드로 이동하는 과정을 반복합니다. 

for(int val : inOrderList) {
            currnetNode.right = new TreeNode(val);
            currnetNode = currnetNode.right;
        }

 

 

 

 

 

이렇게 오늘 18일차 TIL을 작성해 보았습니다.