이진 트리 문제를 해결하는 사고방식은 크게 두 가지 관점으로 요약할 수 있습니다.
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;
}