[LeetCode] Lowest Common Ancestor of a Binary Search Tree

이진 탐색 트리가 주어지고 주어진 이진탐색트리 안에 속해있는 노드 두개가 주어질 때 이 두 노드의 LCA 노드를 리턴하는 문제이다

문제상에서 LCA 노드란 특정 두 노드의 공통부모 노드중 value 가 가장 작은 노드라고 한다 이 때 특정 두 노드중 어느 하나가 LCA가 될 수 있다

Example을 보면

예를 들어 2번 예시에서 p노드가 2 q노드가 4로 주어질 때 이 두노드의 LCA는 p 그 자체인 2가 되는것이다

즉 p와 q노드의 value 값과 현재위치의 value 값을 비교해서 현재위치의 value 값이 p,q노드값의 중간에 있거나

p,q 노드중 한쪽 노드와 값이 같다면 현재 노드가 LCA가 된다

그리하여 루트 노드부터 시작하여 p와 q의 value 둘다 현재 노드의 value보다 작다면 p,q는 현재 노드의 왼쪽 서브트리에 있는것이므로 현재 노드의 왼쪽 자식 노드로 재귀를하고

p,q value 둘다 현재노드의 value 보다 크다면 p,q는 현재 노드의 오른족 서브트리에 있는것이므로 현재 노드의 오른쪽 자식 노드로 재귀를 한다

만약 위의 두 상황이아니라면 현재 노드가 LCA 인것이므로 그대로 return 해준다

const lowestCommonAncestor = function(root, p, q) {
    
    if(p.val < root.val && q.val < root.val) {
        return lowestCommonAncestor(root.left, p, q);
    }
    
    if(p.val > root.val && q.val > root.val) {
        return lowestCommonAncestor(root.right, p, q);
    }
    
    return root
};

submit을 해보니

정답이었다!