트리

/* ── 이진 트리 노드 ─────────────────────────────────────── */
public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

/* ── 레벨 순서로 채워 넣는 완전 이진 트리 구성 ─────────────── */
// 배열 인덱스 i의 자식은 2i+1(왼쪽), 2i+2(오른쪽)에 대응합니다.
public class BinaryTree {
    TreeNode root;

    public TreeNode buildFromArray(int[] values) {
        if (values.length == 0) return null;
        TreeNode[] nodes = new TreeNode[values.length];
        for (int i = 0; i < values.length; i++) {
            nodes[i] = new TreeNode(values[i]);
        }
        for (int i = 0; i < values.length; i++) {
            int leftIdx = 2 * i + 1;
            int rightIdx = 2 * i + 2;
            if (leftIdx < values.length)  nodes[i].left  = nodes[leftIdx];
            if (rightIdx < values.length) nodes[i].right = nodes[rightIdx];
        }
        root = nodes[0];
        return root;
    }
}

/* ── 전위 순회: Root → Left → Right ─────────────────────── */
public void preorder(TreeNode node, List<Integer> result) {
    if (node == null) return;       // 재귀 종료 조건
    result.add(node.value);                 // 1. 루트 방문
    preorder(node.left, result);          // 2. 왼쪽 서브트리
    preorder(node.right, result);         // 3. 오른쪽 서브트리
}

/* ── 중위 순회: Left → Root → Right ─────────────────────── */
public void inorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    inorder(node.left, result);           // 1. 왼쪽 서브트리
    result.add(node.value);                 // 2. 루트 방문
    inorder(node.right, result);          // 3. 오른쪽 서브트리
}

/* ── 후위 순회: Left → Right → Root ─────────────────────── */
public void postorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    postorder(node.left, result);         // 1. 왼쪽 서브트리
    postorder(node.right, result);        // 2. 오른쪽 서브트리
    result.add(node.value);                 // 3. 루트 방문
}

/* ── 호출 예시 ──────────────────────────────────────────── */
List<Integer> result = new ArrayList<>();
preorder(root, result);
// result: [루트, 왼쪽 서브트리 전위, 오른쪽 서브트리 전위] 순서로 채워집니다.

/* ── 레벨 순회: 큐를 이용한 너비 우선 탐색 ──────────────── */
// 전위·중위·후위가 깊이 우선(DFS)인 것과 달리, 레벨 순회는 큐 기반 BFS입니다.
public void levelOrder(TreeNode root, List<Integer> result) {
    if (root == null) return;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.value);
        if (node.left  != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}