수 많은 우문은 현답을 만든다

(Medium) BST LCA 구하기 본문

코딩테스트/Tree

(Medium) BST LCA 구하기

aiden.jo 2023. 10. 26. 01:07

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

 

'코딩테스트 > Tree' 카테고리의 다른 글

(Medium) 허프만 코딩  (0) 2023.11.06
(Medium) BST 여부 검증  (0) 2023.10.26
(Easy) 트리 높이 구하기  (0) 2023.10.24
(Easy) Maximum Depth of Binary Tree  (0) 2023.06.18
(Easy) Invert Binary Tree  (0) 2023.06.18