이진 트리 중위순회

✏️오늘의 문제

💡나의 풀이

---

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>(); // 결과를 저장할 리스트 생성
        helper(root, res); // 재귀 함수 호출
        return res; // 결과 리스트 반환
    }

    public void helper(TreeNode root, List<Integer> res) {
        if (root != null) { // 현재 노드가 null이 아닐 때
            helper(root.left, res); // 왼쪽 서브트리 방문
            res.add(root.val); // 현재 노드의 값 추가
            helper(root.right, res); // 오른쪽 서브트리 방문
        }
    }
}

주요 구성 요소

1. 클래스 및 메소드 정의

   • class Solution: 문제 해결을 위한 클래스를 정의합니다.
   • public List<Integer> inorderTraversal(TreeNode root): 중위 순회를 수행하는 메소드로, 트리의 루트 노드를 인자로 받습니다.

2. 결과 저장

   • List<Integer> res = new ArrayList<>();: 중위 순회 결과를 저장할 리스트를 생성합니다.

3. 재귀 호출

   • helper(root, res);: 중위 순회를 수행하는 헬퍼 메소드를 호출합니다.

4. 헬퍼 메소드

   • public void helper(TreeNode root, List<Integer> res): 재귀적으로 노드를 방문하며 결과를 리스트에 추가합니다.
   • if (root != null): 현재 노드가 null이 아닐 경우에만 진행합니다.
   • helper(root.left, res);: 왼쪽 서브트리를 먼저 방문합니다.
   • res.add(root.val);: 현재 노드의 값을 리스트에 추가합니다.
   • helper(root.right, res);: 오른쪽 서브트리를 방문합니다.
     
     

중위 순회의 특징

• 중위 순회를 통해 이진 트리의 노드를 방문하면, 결과는 항상 오름차순으로 정렬된 형태로 나옵니다. 이는 이진 탐색 트리(BST)의 특성 때문입니다.
• 재귀적 접근을 사용하여 코드가 간결하고 이해하기 쉬운 장점이 있습니다.
  
  

사용 예시

이 코드를 사용하여 이진 트리를 중위 순회하고 결과를 출력할 수 있습니다.

    1
   / \
  2   3

위 트리에서 중위 순회를 수행하면, 결과는 [2, 1, 3]가 됩니다.

➕ 추가 설명

---

추가 설명 및 관련 개념

1. 이진 트리의 구조

   • 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리입니다. 노드는 데이터와 왼쪽, 오른쪽 자식에 대한 포인터를 가지고 있습니다.
   • TreeNode 클래스는 일반적으로 다음과 같이 정의됩니다:

     class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }

2. 재귀의 장점

   • 재귀를 사용하면 코드가 간결하고 읽기 쉬워집니다. 복잡한 반복문 없이도 트리를 쉽게 탐색할 수 있습니다.
   • 각 재귀 호출은 트리의 서브트리를 처리하므로, 전체 트리를 순회하는 데 유용합니다.

3. 시간 복잡도

   • 이진 트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 수입니다.
   • 각 노드에 대해 상수 시간 O(1) 작업을 수행하므로, 전체 시간은 노드 수에 비례합니다.

4. 공간 복잡도

   • 재귀 호출 스택을 고려할 때, 최악의 경우(편향된 트리의 경우) 공간 복잡도는 O(n)입니다. 균형 잡힌 트리에서는 O(log n)입니다.

5. 비재귀적 접근

   • 중위 순회를 비재귀적으로 구현할 수도 있습니다. 스택을 사용하여 현재 노드를 추적하고, 노드를 방문할 때마다 스택에 추가하고 제거하는 방식을 사용할 수 있습니다.

   • 아래는 비재귀적 중위 순회 구현 예시입니다

     public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> res = 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(); // 스택에서 노드 꺼내기
             res.add(current.val); // 노드 값 추가
             current = current.right; // 오른쪽 자식으로 이동
         }
         return res;
     }

6. 적용 사례

   • 이진 탐색 트리(BST)에서 중위 순회는 데이터를 정렬된 순서로 출력하는 데 유용합니다.
   • 중위 순회는 특정 조건을 만족하는 노드를 찾거나, 노드 값을 정렬된 리스트로 변환하는 등의 작업에도 활용됩니다.

7. 유사한 순회 방법

   • 전위 순회(Preorder Traversal): 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리.
   • 후위 순회(Postorder Traversal): 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드.