이진 트리 알고리즘 핵심 유형 분석 및 구현 가이드

이진 트리 문제를 해결하는 사고방식은 크게 두 가지 관점으로 요약할 수 있습니다. 1. **순회(Traversal)의 관점**: 트리의 각 노드를 방문하면서 외부 변수나 상태를 업데이트하여 정답을 구하는 방식입니다. 주로 `traverse` 함수와 전역/멤버 변수를 활용합니다. 2. **분할 정복(Divide and Conquer)의 관점**: 하위 트리(자식 노드)의 결과를 바탕으로 현재 노드의 정답을 도출하는 방식입니다. 함수의 반환값을 적극적으로 활용하여 문제를 작은 단위로 쪼개어 해결합니다. 어떤 방식을 선택하든 핵심은 **"현재 노드에서 무엇을 처리해야 하는가?"**와 **"그 처리를 언제(전위/중위/후위) 수행해야 하는가?"**를 정의하는 것입니다. 이진 트리의 기본 구조는 다음과 같이 정의됩니다.
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;
    }
}

1. 이진 트리의 레벨 순회 (BFS)

트리를 층별로 탐색하는 전형적인 너비 우선 탐색(BFS) 문제입니다. 큐(Queue)를 활용하여 각 레벨의 노드들을 순차적으로 처리합니다.
public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

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

    while (!nodeQueue.isEmpty()) {
        int currentLevelSize = nodeQueue.size();
        List<Integer> currentLevelNodes = new ArrayList<>();

        for (int i = 0; i < currentLevelSize; i++) {
            TreeNode node = nodeQueue.poll();
            currentLevelNodes.add(node.val);

            if (node.left != null) nodeQueue.offer(node.left);
            if (node.right != null) nodeQueue.offer(node.right);
        }
        result.add(currentLevelNodes);
    }
    return result;
}

2. 이진 트리의 최근 공통 조상 (LCA)

두 노드 `p`와 `q`의 가장 가까운 공통 조상을 찾는 문제입니다. 하위 트리에서 `p`나 `q`가 발견되는지 여부를 반환받아 처리하는 분할 정복 방식을 사용합니다.
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }

    TreeNode leftFound = lowestCommonAncestor(root.left, p, q);
    TreeNode rightFound = lowestCommonAncestor(root.right, p, q);

    if (leftFound != null && rightFound != null) {
        return root;
    }
    return leftFound != null ? leftFound : rightFound;
}

3. 지그재그 레벨 순회

레벨 순회를 수행하되, 층마다 탐색 방향을 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 번갈아 변경합니다. `LinkedList`의 `addFirst`와 `addLast`를 활용하면 효율적입니다.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> zigzagResult = new ArrayList<>();
    if (root == null) return zigzagResult;

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

    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> levelValues = new LinkedList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (reverseDirection) {
                levelValues.addFirst(node.val);
            } else {
                levelValues.addLast(node.val);
            }
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        zigzagResult.add(levelValues);
        reverseDirection = !reverseDirection;
    }
    return zigzagResult;
}

4. 이진 트리 최대 경로 합

노드 간의 경로 중 합이 최대가 되는 값을 구합니다. 후위 순회를 통해 각 노드가 부모에게 제공할 수 있는 최대 기여도를 계산하며 전역 최댓값을 갱신합니다.
class PathSumSolution {
    private int globalMax = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        calculateContribution(root);
        return globalMax;
    }

    private int calculateContribution(TreeNode node) {
        if (node == null) return 0;

        int leftMax = Math.max(0, calculateContribution(node.left));
        int rightMax = Math.max(0, calculateContribution(node.right));

        globalMax = Math.max(globalMax, node.val + leftMax + rightMax);
        return node.val + Math.max(leftMax, rightMax);
    }
}

5. 이진 트리 중위 순회 (Inorder Traversal)

왼쪽 자식, 현재 노드, 오른쪽 자식 순으로 방문합니다.
public List<Integer> inorderTraversal(TreeNode root) {
    List<Integer> path = new ArrayList<>();
    executeInorder(root, path);
    return path;
}

private void executeInorder(TreeNode node, List<Integer> path) {
    if (node == null) return;
    executeInorder(node.left, path);
    path.add(node.val);
    executeInorder(node.right, path);
}

6. 이진 트리의 우측 뷰 (Right Side View)

각 레벨에서 가장 오른쪽에 위치한 노드들만 추출합니다. BFS를 사용하거나, 오른쪽 자식을 먼저 방문하는 DFS로 해결할 수 있습니다.
public List<Integer> rightSideView(TreeNode root) {
    List<Integer> visibleNodes = new ArrayList<>();
    dfsRightView(root, 0, visibleNodes);
    return visibleNodes;
}

private void dfsRightView(TreeNode node, int depth, List<Integer> result) {
    if (node == null) return;
    if (depth == result.size()) {
        result.add(node.val);
    }
    dfsRightView(node.right, depth + 1, result);
    dfsRightView(node.left, depth + 1, result);
}

7. 전위 및 중위 순회 결과를 이용한 트리 복원

전위 순회(Preorder)의 첫 번째 요소가 루트임을 이용하고, 중위 순회(Inorder)에서 루트의 위치를 찾아 좌우 서브 트리를 재귀적으로 생성합니다.
class TreeBuilder {
    private Map<Integer, Integer> inorderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        return construct(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode construct(int[] preorder, int preStart, int preEnd, int inStart, int inEnd) {
        if (preStart > preEnd) return null;

        int rootVal = preorder[preStart];
        int rootIndex = inorderMap.get(rootVal);
        int leftSize = rootIndex - inStart;

        TreeNode root = new TreeNode(rootVal);
        root.left = construct(preorder, preStart + 1, preStart + leftSize, inStart, rootIndex - 1);
        root.right = construct(preorder, preStart + leftSize + 1, preEnd, rootIndex + 1, inEnd);
        return root;
    }
}

8. 루트에서 잎 노드까지의 숫자 합

경로를 따라가며 숫자를 조합(기존 합 * 10 + 현재 값)하고, 잎 노드에 도달했을 때 그 합을 반환합니다.
public int sumNumbers(TreeNode root) {
    return calculateSum(root, 0);
}

private int calculateSum(TreeNode node, int currentTotal) {
    if (node == null) return 0;
    int nextSum = currentTotal * 10 + node.val;
    if (node.left == null && node.right == null) {
        return nextSum;
    }
    return calculateSum(node.left, nextSum) + calculateSum(node.right, nextSum);
}

9. 이진 트리의 최대 깊이

자식 노드들의 깊이 중 최댓값에 현재 노드의 깊이(1)를 더하여 반환합니다.
public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}

태그: binary-tree java algorithm dfs bfs

10월 23일 20:20에 게시됨