[python] leetcode_235. Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

문제 설명

BST(Binary Search Tree)에서 LCA(Lowest Common Ancestor)을 찾아라.

root : 루트 노드

p, q : 타겟 노드

 

접근 방법

만약(if), p,q가 root보다 작다면 BST의 성질에 따라서 두 노드는 왼쪽 서브트리에 존재한다.

그렇지 않다면(elif), p,q가 root보다 모두 크다면, BST 성질에 따라서 두 노드는 오른쪽 서브트리에 존재한다.

그마저 아니라면(else) p,q 사이에 root가 있으므로 공통 조상은 root가 된다.

 

이 때, 서브트리로 이동했을 때, 재귀문으로 현재 함수를 반복하면 LCA를 구할 수 있다.

 

코드

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        elif p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        else:
            return root

 

후기

처음에 못 풀었다... 답지 보고 풀었지만 더 노력하자