[LeetCode]144. Binary Tree Preorder 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> preorderTraversal(TreeNode root) {
        List<Integer> output = new ArrayList<>();
        if (root == null){
            return output;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()){
            TreeNode cur = stack.pop();
            if (cur.right != null){
                stack.push(cur.right);
            }
            if (cur.left != null){
                stack.push(cur.left);
            }
            output.add(cur.val);
        }
        return output;
    }
}

이진 트리 순회

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

전위 순회 특징

1. 초기화: 루트 노드를 바로 스택에 push합니다.
2. 순회 로직: 현재 노드를 스택에서 pop하고 즉시 처리합니다 (값을 출력하고 결과 리스트에 추가).
   • 오른쪽 자식을 먼저 스택에 push한 다음 왼쪽 자식을 push합니다. 이는 스택의 LIFO(Last In First Out) 특성 때문입니다.
3. 단순화: 전위 순회는 노드를 방문하자마자 처리하므로 이전 방문 정보를 추적할 필요가 없습니다.
4. null 체크: 루트가 null인 경우를 처리하여 예외 상황을 방지합니다.