[이진 트리 (Binary Tree)] LC #94 Binary Tree Inorder Traversal

문제 설명

Given the root of a binary tree, return the inorder traversal of its nodes' values.

 

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

 

Constraints:

Follow up: Recursive solution is trivial, could you do it iteratively?

문제 링크: https://leetcode.com/problems/binary-tree-inorder-traversal/

1. 문제의 핵심: 중위 순회(Inorder Traversal)의 이해

트리 순회 3대장(전위, 중위, 후위) 중 하나인 중위 순회는 "왼쪽 서브트리 → 루트(자기 자신) → 오른쪽 서브트리" 순서로 노드를 방문하는 깊이 우선 탐색(DFS)의 한 종류입니다. 이 순서 때문에, 이진 검색 트리(BST)에 중위 순회를 적용하면 노드 값들이 오름차순으로 정렬되어 나온다는 중요한 특징이 있습니다.

핵심 아이디어: 재귀적으로 왼쪽 끝까지 파고든 후, 돌아오면서 노드를 방문하고, 그 다음 오른쪽으로 이동하는 패턴을 구현한다.

2. 해결 전략

문제의 Follow-up에서 재귀적 풀이와 반복적 풀이를 모두 요구하고 있습니다.

방법 1: 재귀(Recursion)를 이용한 풀이 (직관적인 방법)

  1. 결과를 담을 `List`를 생성합니다.
  2. 재귀적으로 동작할 헬퍼(helper) 함수를 만들고, 현재 노드와 결과 리스트를 인자로 받습니다.
  3. 헬퍼 함수 로직:
    • 현재 노드가 `null`이면 즉시 종료합니다.
    • 왼쪽 자식에 대해 헬퍼 함수를 재귀 호출합니다.
    • 현재 노드의 값을 결과 리스트에 추가합니다.
    • 오른쪽 자식에 대해 헬퍼 함수를 재귀 호출합니다.

방법 2: 반복(Iteration)과 스택(Stack)을 이용한 풀이

  1. 결과 리스트와 노드를 담을 `Stack`을 생성합니다.
  2. `current` 포인터를 `root`로 초기화합니다.
  3. `current`가 `null`이 아니거나 스택이 비어있지 않은 동안 반복합니다.
    • `while (current != null)`: `current`를 스택에 push하고, `current`를 왼쪽 자식으로 계속 이동시킵니다. (가장 왼쪽 노드까지 탐색)
    • `current`가 `null`이 되면 (더 이상 왼쪽으로 갈 수 없으면), 스택에서 노드를 pop하여 `current`에 할당합니다.
    • `current`의 값을 결과 리스트에 추가합니다. (방문 처리)
    • `current`를 `current`의 오른쪽 자식으로 설정하여 오른쪽 서브트리 탐색을 준비합니다.

3. Java 코드 구현

재귀적 풀이 (Recursive)

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

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List<Integer> list) {
        if (node == null) {
            return;
        }
        // 1. 왼쪽 서브트리 순회
        traverse(node.left, list);
        // 2. 루트 노드 방문
        list.add(node.val);
        // 3. 오른쪽 서브트리 순회
        traverse(node.right, list);
    }
}

반복적 풀이 (Iterative)

import java.util.ArrayList;
import java.util.List;
import java.util.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()) {
            // 1. 가장 왼쪽 노드까지 스택에 담으며 이동
            while (current != null) {
                stack.push(current);
                current = current.left;
            }

            // 2. 스택에서 노드를 꺼내 방문 (리스트에 추가)
            current = stack.pop();
            result.add(current.val);

            // 3. 오른쪽 서브트리 탐색 준비
            current = current.right;
        }
        return result;
    }
}

💡 코드 세부 포인트