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;
        }
    }
}

[회고]

재귀 알고리즘은 뭔가 풀어도 시원하지가 않은 것 같습니다.

 

 

 

 

질문과 피드백은 언제나 환영입니다.

감사합니다.