CodingTest/LeetCode
[LeetCode] 2895. Minimum Processing Time
창브로
2025. 3. 16. 17:22
[문제 링크]
https://leetcode.com/problems/minimum-processing-time/description/
[문제]
이진트리에서 두 노드 p와 q가 주어졌을 때, 이 둘의 최소 공통 조상(LCA)을 찾는 문제입니다.
최소 공통 조상이란?
트리에서 두 노드 p와 q를 모두 자손으로 포함하는 가장 낮은(가장 깊은) 노드를 의미합니다. 즉, p와 q가 다른 서브트리에 있다면 그들의 부모가 LCA가 됩니다. 한쪽이 다른 쪽의 조상이라면, 조상 노드가 그대로 LCA가 됩니다.
- 입력
root: 이진 트리의 루트 노드 p, q: 트리 내 존재하는 두 노드 (항상 트리 내에 존재함)
- 출력
p와 q의 최소 공통 조상(TreeNode 객체)을 반환
[풀이 과정]
처음에 어떤식으로 풀어야 하지?라고 생각을 하며 간단한 방법을 떠올렸습니다.

그냥 무식하게 풀어보니 패턴이 나오게 되어 구현하게 되었습니다.
결론은 결국 답을 구하려면 모든 노드를 탐색하여야 합니다.
근데 노드를 탐색하는 건 똑같은 방법을 반복하는 일입니다.
문제에서 주어진건 root기 때문에 root에서 아래로 그냥 계속 아래인 자식 노드들이 점화식을 통해 답을 구해 올라오게 만들어
해결하는 방법을 선택하였습니다.
[코드]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q) {
return root;
}
// 재귀 사용
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// left도 null이 아니고 right도 null이 아니면 지금 root가 공통 조상
if(left != null && right != null) {
return root;
}
// left만 null 이면 right가 p,q 중 하나의 조상
// right만 null 이면 left가 p,q 중 하나의 조상
if(left == null) {
return right;
} else {
return left;
}
}
}
[회고]
재귀 알고리즘은 뭔가 풀어도 시원하지가 않은 것 같습니다.
질문과 피드백은 언제나 환영입니다.
감사합니다.