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

 

 

오늘의 문제는 LeetCode

 

Binary Tree Inorder Traversal

 

 

문제

 

 

 

문제 설명 

 

이진 트리의 루트가 주어집니다. 이를 중위 순회한 결과를 반환하면 되는 문제입니다. 

예를 들어 입력 값이 root = [1, null, 2, 3] 일 때의 결과 값은 [1, 3, 2] 입니다.

 

 

 

문제 풀이 시간 

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

 

 

 

문제 접근 방식

DFS의 재귀를 통한 방식을 사용했습니다. 

문제에서 List가 주어졌기 때문에 순회 결과를 저장할 리스트를 생성합니다. 재귀 함수를 사용해 중위 순회를 수행합니다. 먼저 노드가 null이 아니면 왼쪽 자식 노드를 방문합니다. 그 다음 현재 노드의 값을 리스트에 저장합니다. 다음으로 오른쪽 자식 노드에 방문합니다. 

이러한 재귀 호출을 거치면 순회 결과가 리스트에 저장 됩니다. 

 

 

 

문제 풀이(재귀)

import java.util.ArrayList;
import java.util.List; 

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>();     
        
        inorder(root, answer);   
        return answer;           
    }

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

 

문제 풀이(반복문)

import java.util.ArrayList;
import java.util.List;
import java.util.Stack; 

/**
 * 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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> answer = new ArrayList<>(); 
        Stack<TreeNode> stack = new Stack<>();  
        TreeNode current = root; 

        
        while(current != null || !stack.isEmpty()) {   
            while(current != null) {
                stack.push(current);      
                current = current.left;   
            }
            current = stack.pop();      
            answer.add(current.val);    
            current = current.right;    
        } 

        return answer;
    }
}

 

 

중위 순회 알아보기 

이진 트리의 순회 방식에는 전위 순회, 중위 순회, 후위 순회가 있습니다. 각 순회는 부모 노드의 우선순위가 몇 번째인지에 따라 구분됩니다. 

• 전위 순회(PreOrder) : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
• 중위 순회(InOrder) : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드  
• 후위 순회(PostOrder) : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 

 

 

깊이 우선 탐색(DFS) 사용하기 

깊이 우선 탐색은 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. 

깊이 우선 탐색은 재귀를 사용하기 때문에 탐색 공간의 깊이가 제한 되어 있는 경우에 사용해야 합니다.

또한 탐색 공간 내 탐색 목표가 있을 때 사용합니다. 

 

 

 

반복문을 이용한 풀이 알아보기 

반복문을 사용한 중위 순회에서는 이중 while문을 사용하는데 이를 자세히 알아봅시다. 

 

1. 외부 while문 

• current 가 nul.l 이 아니거나 stack 이 비어있지 않은 동안 반복합니다. 즉, 트리의 모든 노드를 방문할 때까지 실행됩니다. 
• current 가 null 이 된 경우에도 stack 에 노드가 남아 있을 수 있기 때문에 스택이 비어 있지 않으면 순회가 계속됩니다. 

2. 내부 while문

• current 가 null 이 아닐 때까지 현재 노드의 왼쪽 자식을 스택에 추가합니다. 즉, 트리의 가장 왼쪽 끝에 도달할 때까지 반복됩니다. 
• 현재 노드가 null 이 되면 내부 while 문이 종료 됩니다. 이후에 스택에서 노드를 꺼내 current 를 오른쪽 자식으로 설장한 뒤 외부 while 문으로 돌아갑니다. 

 

 

 

 

 

 

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