오늘의 학습 키워드
</> 깊이/너비 우선 탐색(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 {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorderTree(root, result);
return result;
}
private void inorderTree(TreeNode node, List<Integer> result){
if (node == null){
return;
}
inorderTree(node.left, result);
result.add(node.val);
inorderTree(node.right, result);
}
}오늘의 회고
오늘 주제는 깊이/너비 우선 탐색이었다. 문제를 번역 해보았을때 나온것은 이진트리의 중위순회라고 나와있어서 우선 중위순회가 무엇인지 부터 검색을 시작했다.
순회방법에는 전위순회, 중위순회, 후위순회가 있다고 한다. 각 순회방법들은 다음과 같은 방법으로 노드를 순회한다
전위 순회는 Root-Left-Right
중위 순회는 Left-Root-Right
후위 순회는 Left-Right-Root
트리를 순회하는 방법은 주로 재귀적으로 구현된다.
재귀를 통해 트리의 노드를 방문하면서 순회를 수행할 수 있다.
또한, 스택(Stack)이나 큐(Queue)를 이용하여 반복적으로 순회할 수도 있다.
그래서 나는 오늘 공부하면서 봤던 코드로 중위순회를 하는 코드를 먼저 작성했다.
private void inorderTree(TreeNode node, List<Integer> result){
//노드가 null일 경우 즉시 리턴
if (node == null){
return;
}
//왼쪽 노드 순회
inorderTree(node.left, result);
//현재 노드값 저장
result.add(node.val);
//오른쪽 노드 순회
inorderTree(node.right, result);
}그리고 결과를 담아서 반환해줄 리스트가 필요했고 ArrayList로 생성을 하였다.
List<Integer> result = new ArrayList<>();그리고 만들어 놓은 중위 순회를 재귀적으로 수행하기 위한 함수를 호출한다.
inorderTree(root, result);이것으로 함수내에서 result가 수정되게 되면 원본 리스트가 직접 수정이 되게 된다.
그리고 모든 순회가 종료되고 나서 최종적으로 result리스트가 반환이 된다.
return result;오늘 이진트리가 탐색되는 과정에 대해서 매우 햇갈리고 왜 이런것일까에 대해 고민도 많이 하고 검색도 많이하면서 상당부분 이해가 된 것 같다.
처음에는 중위 순회하는 함수를 만들어 놓았으니 종료가 되면 다시 이전 노드로 돌아가서 왼쪽탐색을 다시하고 현재 노드값을 저장하고 오른쪽 노드를 탐색한다고 생각해서 논리적인 문제가 컸던 것 같다. 그래서 지금 내가 최종적으로 이해한것은 왼쪽노드를 연속적으로 탐색하고 null일 경우 null을 기준으로 왼쪽노드를 탐색하기 이전 노드를 현재노드로 두고 그 값을 반환해주고 다음단계로 오른쪽노드를 순회해준다. 이렇게 반복을 하다 오른쪽 노드의 순회가 종료 되었으면 이전 노드로 돌아가게 되는데 그 노드는 이미 왼쪽 노드 순회가 끝난 상태이기 때문에 바로 리스트로 반환해주고 다음단계로 오른쪽 노드가 순회된다는 결론에 이르게 되었다.
아직 이진트리나 재귀적 함수 등에 기본적인 지식이 없어 과정에 대한 의문을 더 복잡하게 가졌던게 아닐까 생각이 든다.
AI 코드리뷰
현재 코드의 장점
- 간결하고 이해하기 쉬운 재귀적 구현
- 코드가 직관적이며 중위 순회의 로직을 명확히 표현함
- 추가 메모리 사용이 적음 (call stack 제외)
현재 코드의 단점
- 재귀 호출로 인한 stack overflow 가능성 (매우 깊은 트리의 경우)
- 큰 트리에서는 재귀 호출로 인한 오버헤드 발생 가능
시간 복잡도
- 시간 복잡도: O(n), 여기서 n은 트리의 노드 수
- 공간 복잡도: O(h), 여기서 h는 트리의 높이 (최악의 경우 O(n))
개선된 코드 제안 (반복적 접근 - Stack 사용)
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = 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();
result.add(current.val);
current = current.right;
}
return result;
}
}개선된 버전의 장점:
- 스택 오버플로우 위험이 없음
- 매우 깊은 트리에서도 안정적으로 동작
- 일부 상황에서 재귀 방식보다 성능이 좋을 수 있음
개선된 버전의 단점:
- 코드가 재귀 방식보다 약간 더 복잡함
- 명시적인 스택 사용으로 추가 메모리 필요
시간 복잡도:
- 시간 복잡도: O(n), 여기서 n은 트리의 노드 수
- 공간 복잡도: O(h), 여기서 h는 트리의 높이 (최악의 경우 O(n))
두 방법 모두 시간 복잡도는 동일하지만, 반복적 방법은 매우 깊은 트리에서 스택 오버플로우 위험이 없다는 장점이 있습니다.
Queue를 사용한 방법:
중위 순회는 일반적으로 Queue를 직접 사용하여 구현하지 않습니다. Queue는 주로 너비 우선 탐색(BFS)에 사용됩니다. 하지만 중위 순회의 결과를 저장하는 데 Queue를 사용할 수는 있습니다. 그러나 이는 단순히 결과 저장 구조를 바꾸는 것일 뿐, 알고리즘의 본질적인 부분은 아닙니다.
결론적으로, 재귀적 방법과 Stack을 사용한 반복적 방법이 중위 순회를 구현하는 가장 일반적이고 효율적인 방법입니다. 트리의 깊이가 매우 깊지 않다면 재귀적 방법이 더 간단하고 이해하기 쉽지만, 매우 깊은 트리를 다룰 때는 반복적 방법이 더 안전할 수 있습니다.
내일 공부할 것 :
- 트리 순회의 다른 방법들:
- 전위 순회(preorder traversal)
- 후위 순회(postorder traversal)
- 레벨 순서 순회(level-order traversal)
- 트리 관련 다른 알고리즘:
- 이진 탐색 트리(Binary Search Tree) 구현 및 연산
- 균형 이진 트리(예: AVL 트리, 레드-블랙 트리)
- 트리의 높이 또는 깊이 계산
- 그래프 알고리즘:
- 깊이 우선 탐색(DFS)
- 너비 우선 탐색(BFS)
- 최단 경로 알고리즘(다익스트라, 벨만-포드 등)
- 자료구조 심화:
- 힙(Heap)과 우선순위 큐
- 해시 테이블 구현 및 충돌 해결 방법
- 알고리즘 복잡도 분석:
- 시간 복잡도와 공간 복잡도의 깊이 있는 이해
- 다양한 알고리즘의 복잡도 분석 연습
문제
https://leetcode.com/problems/binary-tree-inorder-traversal/
