LeetCode 236. Lowest Common Ancestor of a Binary Tree 자바 문제 풀이

문제

Lowest Common Ancestor of a Binary Tree - LeetCode

문제 해결 방법

• 최소공통 조상LCA를 알고 있느냐고 묻고, 이를 구현할수 있느냐고 묻는 문제입니다.
• LCA의 전처리 과정은 이 문제에서는 사용할수 없습니다. Tree Node를 수정할수 없기떄문입니다.
• 그러므로, 보통 LCA알고리즘은 목표로하는 두 노드에서 부모로 올라가며 비교하는 방식이지만, 이 문제의 경우 root에서 하나씩 아래로 내려가며, p나 q가 현재 노드와 같은가 비교하여 구합니다.

참고

최소 공통 조상, LCA(Lowest Common Ancestor)이란

Github Link

https://github.com/eunhanlee/LeetCode_236_LowestCommonAncestorofaBinaryTree_Solution.git

시간복잡도: O(n), 공간복잡도: O(n)

n=이진트리의 깊이

public class Solution {
    /**
     * 이진 트리에서 두 노드의 가장 낮은 공통 조상을 찾습니다.
     *
     * @param root 이진 트리의 루트 노드입니다.
     * @param p    첫 번째 노드입니다.
     * @param q    두 번째 노드입니다.
     * @return 노드 p와 q의 가장 낮은 공통 조상입니다.
     */
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 루트가 null이거나 p 또는 q가 루트인 경우, 루트를 반환합니다.
        if (root == null || root == p || root == q) {
            return root;
        }

        // 왼쪽 서브트리와 오른쪽 서브트리에서 재귀적으로 가장 낮은 공통 조상을 찾습니다.
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // leftLCA와 rightLCA가 모두 null이 아닌 경우, p와 q가 서로 다른 서브트리에 있는 것이므로 현재 루트가 가장 낮은 공통 조상입니다.
        if (leftLCA != null && rightLCA != null) {
            return root;
        }
        // leftLCA가 null이 아닌 경우, p와 q가 왼쪽 서브트리에 있는 것이므로 가장 낮은 공통 조상은 왼쪽 서브트리에 있습니다.
        else if (leftLCA != null) {
            return leftLCA;
        }
        // rightLCA가 null이 아닌 경우, p와 q가 오른쪽 서브트리에 있는 것이므로 가장 낮은 공통 조상은 오른쪽 서브트리에 있습니다.
        else {
            return rightLCA;
        }
    }
}

코드 순서 예제

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.