LeetCode - Lowest Common Ancestor

문제

💡 이진 트리의 노드에서 특정한 값인 p와 q가 주어졌을 때, 그 두 노드의 가장 가까운 공통 조상을 찾으시오.

예시

• Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
• Output: 3

제약 조건

• 트리의 노드 수는 [2, 10^5] 범위 안에 있습니다.
• -10^9부터 10^9까지의 Node.val 값이 존재합니다.
• 모든 Node.val 값은 고유합니다.
• p와 q는 서로 다른 노드이며, 트리 안에 존재할 것입니다.

풀이

문제 이해하기

• 시간복잡도를 계산한기 위한 N은 트리의 노드 갯수다.
• input의 최댓값에 따라 N^2 보다 작은 시간복잡도를 가진 알고리즘을 선택해야한다.
• Node의 value 값의 범위는 int 형 변수에 담을 수 있다.

접근 방법 생각하기

1. 트리를 탐색하면서 P와 Q를 찾는다.
2. P나 Q를 찾았다면 상위 노드에 알린다.
3. 한쪽 서브트리에서 노드를 찾았다는 알림이 오면 상위 노드로 알린다.
4. 양쪽 서브트리에서 노드를 찾았다는 알림이 오면 그 노드가 공통 조상이된다.

코드 설계

1. DFS를 사용하여 트리를 순회한다.
2. 방문한 노드의 값이 p나 q와 같다면 그 노드를 반환한다.
3. 왼쪽 서브트리에서만 발견된다면 왼쪽 서브트리에서 찾은 노드를 반환하고, 오른쪽 서브트리에서만 발견된다면 오른쪽 서브트리에서 찾은 노드를 반환한다.
4. 왼쪽 서브트리와 오른쪽 서브트리에서 각각 p와 q가 발견되면 그 노드를 반환한다.

코드 구현

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }

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

        if (root.val == p.val || root.val == q.val) {
            return root;
        }
        if (left != null && right != null) {
            return root;
        }
        if (left != null) {
            return left;
        }
        return right;
    }
}