(Medium) BST LCA 구하기

Binary Search Tree : Lowest Common Ancestor 구하기

 

문제링크

 

Input

6
4 2 3 1 7 6
1 7

Output
[reference to node 4]

 

풀이 :

def lca(root, v1, v2):

    

    if not root:

        return None

    
    // BST 특성상 작은게 루트의 왼쪽에 있다면 무조건 왼쪽 탐색

    if v1 < root.info and v2 < root.info:

        return lca(root.left, v1, v2)

    elif v1 > root.info and v2 > root.info:

        return lca(root.right, v1, v2)

    
    //찾고자 하는 두개 원소가 양쪽으로 있다고 한다면, 방향에 상관없이 어쨌든 바이너리 트리이자 최소점임     

    else:

        return root