leetcode link

Description

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

---

이진 트리에서 두 주어진 노드의 최소 공통 조상(LCA)을 찾습니다.

Wikipedia에 따른 LCA의 정의에 따르면: "두 노드 p와 q에 대한 최소 공통 조상은 T 내에서 p와 q 둘 다의 자손이 되는 가장 낮은 노드로 정의됩니다(여기서 노드가 자기 자신의 자손이 될 수 있음을 허용합니다)."

예제 1:

입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
출력: 3
설명: 노드 5와 1의 LCA는 3입니다.

예제 2:

입력: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
출력: 5
설명: 노드 5와 4의 LCA는 5입니다, LCA 정의에 따라 노드는 자기 자신의 자손이 될 수 있습니다.

예제 3:

입력: root = [1,2], p = 1, q = 2
출력: 1

제약 조건:

• 트리의 노드 수는 [2, 10^5] 범위에 있습니다.
• -10^9 <= Node.val <= 10^9
• 모든 Node.val은 유일합니다.
• p != q
• p와 q는 트리에 존재합니다.

Solution 1

class Solution {
    // 세 개의 전역 변수 선언: 두 타겟 노드 p, q와 최소 공통 조상 노드
    TreeNode p;
    TreeNode q;
    TreeNode lowestCommonAncestorNode;

    // 주어진 루트 노드와 두 타겟 노드를 사용하여 최소 공통 조상을 찾는 메서드
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.p = p;
        this.q = q;
        dfs(root); // 깊이 우선 탐색을 시작하여 최소 공통 조상을 찾음

        return lowestCommonAncestorNode; // 찾은 최소 공통 조상 노드 반환
    }

    // 깊이 우선 탐색(DFS)을 수행하는 메서드
    TreeNode dfs(TreeNode node) {
        if (node == null) // 탐색 중인 노드가 null이면 탐색 종료
            return null;

        TreeNode left = dfs(node.left); // 왼쪽 자식 노드로의 DFS 수행
        TreeNode right = dfs(node.right); // 오른쪽 자식 노드로의 DFS 수행
        // 주석 제거: 현재 노드와 자식 노드들의 값을 출력하는 불필요한 출력문

        if (node == p || node == q) { // 현재 노드가 p 또는 q와 일치하면
            if (left != null || right != null) {
                lowestCommonAncestorNode = node; // 만약 왼쪽 또는 오른쪽 자식이 이미 찾은 경우, 현재 노드가 LCA임
                return null;
            }
            return node; // p 또는 q를 찾았으나, 다른 하나는 아직 찾지 못한 경우 현재 노드 반환

        } else { // 현재 노드가 p 또는 q가 아닌 경우
            if (left != null && right != null) {
                lowestCommonAncestorNode = node; // 왼쪽과 오른쪽 모두에서 타겟 노드를 찾았다면, 현재 노드가 LCA임
            } else if (left != null) {
                return left; // 왼쪽 자식에서만 타겟 노드를 찾았다면, 왼쪽 자식 반환
            } else if (right != null) {
                return right; // 오른쪽 자식에서만 타겟 노드를 찾았다면, 오른쪽 자식 반환
            }
            return null; // 타겟 노드를 찾지 못했다면 null 반환
        }
    }
}

Solution 2

불필요한 전역 변수를 제거하고, DFS 함수 내에서 직접 최소 공통 조상을 찾아 반환하는 방식으로 개선함.

이 코드는 다음 원리에 기반합니다:

• 현재 노드가 p나 q와 같다면, 현재 노드를 반환합니다. 이는 p 또는 q를 찾았음을 의미합니다.
• 현재노드가 p 나 q일때 다른 자식 노드p 또는 q를 자식으로 가지면 최소 공통 조상으로 간주됩니다. 아니라면 최소 공통 조상이 상위 노드에 있고 이는 다음 탐색에서 찾아집니다.
• 왼쪽과 오른쪽 자식 노드를 재귀적으로 탐색합니다.
• 만약 양쪽 자식 노드에서 각각 p와 q를 찾았다면, 현재 노드가 p와 q의 최소 공통 조상입니다.
• 하나의 자식 노드만 p 또는 q를 찾았다면, 그 자식 노드를 반환합니다.
• 이 방식으로 최소 공통 조상을 효율적으로 찾을 수 있습니다.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 직접 dfs 함수 내에서 최소 공통 조상을 찾아 반환
        return dfs(root, p, q);
    }

    private TreeNode dfs(TreeNode node, TreeNode p, TreeNode q) {
        // 기저 사례: 노드가 null이면 탐색 종료
        if (node == null)
            return null;

        // 현재 노드가 p 또는 q와 일치할 경우, 추가 탐색을 중지하고 현재 노드를 반환합니다.
        // 만약 현재 노드가 p 또는 q 중 하나를 자식으로 가지고 있으면, 현재 노드는 최소 공통 조상이 됩니다.
        // 최소 공통 조상이 현재 노드보다 상위에 있으면, 다음 탐색 단계에서 해당 조상 노드가 찾아져 반환됩니다.
        if (node == p || node == q)
            return node;

        // 왼쪽과 오른쪽 자식 노드 탐색
        TreeNode left = dfs(node.left, p, q);
        TreeNode right = dfs(node.right, p, q);

        // 만약 왼쪽과 오른쪽 자식 노드 탐색에서 둘 다 null이 아닌 노드가 반환되었다면, 현재 노드가 LCA임
        if (left != null && right != null)
            return node;

        // 왼쪽이나 오른쪽 자식 노드 중 하나만 null이 아닌 경우, null이 아닌 자식 노드 반환
        return left != null ? left : right;
    }
}