[LeetCode]94. Binary Tree Inorder Traversal

/**
 * 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;
 *     }
 * }
 */
 import java.util.*;
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<>();

        if (root == null){
            return output;
        }

        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (cur != null || !stack.isEmpty()) {

        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        
        cur = stack.pop();
        output.add(cur.val);

        cur = cur.right;
        }
        return output;
    }
}

이진 트리 순회

전위 순회 (Preorder Traversal): "루트 - 왼쪽 - 오른쪽"
중위 순회 (Inorder Traversal): "왼쪽 - 루트 - 오른쪽"
후위 순회 (Postorder Traversal): "왼쪽 - 오른쪽 - 루트"

중위 순회 특징

1. 순회 순서: 중위 순회는 각 노드에 대해 왼쪽 자식을 먼저 방문하고, 그 다음 자신을 방문한 후, 마지막으로 오른쪽 자식을 방문합니다.
2. 이진 검색 트리(BST)와의 관계: 이진 검색 트리에서 중위 순회를 수행하면, 노드들을 오름차순으로 방문하게 됩니다.
3. 대칭성: 중위 순회는 트리의 구조를 대칭적으로 탐색합니다. 이 특성은 트리의 균형을 확인하거나 대칭적인 연산을 수행할 때 유용합니다.

구현 특징

1. 스택 사용: 스택을 사용하여 아직 방문하지 않은 노드들을 저장합니다. 이는 재귀 호출 스택을 명시적으로 관리하는 것과 같습니다.

결론

중위 순회는 이진 트리를 다루는 데 있어 필수적인 기법 중 하나입니다. 그 특유의 순회 순서와 특성으로 인해 다양한 문제 해결에 활용될 수 있습니다.
특히 이진 검색 트리와 관련된 작업에서 그 유용성이 두드러집니다.