[LC] 235. Lowest Common Ancestor of a Binary Search Tree

[seungriyou]

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

Approach

BST(binary search tree)에서는 어떤 node에 대해 다음이 성립한다.

• left subtree: node.val 보다 작은 값들만 존재
• right subtree: node.val 보다 큰 값들만 존재

이러한 점을 이용하면, 다음과 같이 root에서부터 내려가면서 root의 val과 p, q의 val을 비교하며 LCA를 찾아나갈 수 있다.

#	케이스	LCA 위치	동작
1	p.val, q.val이 모두 root.val 보다 작은 경우	left subtree	root -> root.left
2	p.val, q.val이 모두 root.val 보다 큰 경우	right subtree	root -> root.right
3	1, 2번에 모두 해당하지 않는 경우	root	return root

이는 while 문을 통해 iterative 하게도, recursive 하게도 구현 가능하다.

Tip 💡

ref: https://www.geeksforgeeks.org/chaining-comparison-operators-python/

파이썬에서는 비교 연산자를 chaining 하여 사용할 수 있고, 이를 comparison operator chaining라고 한다. 이는 파이썬의 모든 비교 연산자가 동일한 우선 순위를 가지기 때문이며, and로 chaining 된다고 생각하면 된다.

비교 연산자의 종류는 다음과 같다.

">" | "<" | "==" | ">=" | "<=" | "!=" | "is" ["not"] | ["not"] "in"

a op1 b op2 c … y opN z는 a op1 b and b op2 c and … y opN z와 동일하다. 다만, 모든 식이 단 한 번에 평가된다는 점만 다르다!

이번 문제의 코드에서는 다음과 같이 사용하였다.

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    """
    BST에서는 어떤 node에 대해...
    - left subtree: node.val 보다 작은 값들만 존재
    - right subtree: node.val 보다 큰 값들만 존재
    """
    while root:
        # (1) p, q가 모두 root.val 보다 작으면, LCA는 left subtree에 위치
        if p.val < root.val > q.val:
            root = root.left

        # (2) p, q가 모두 root.val 보다 크면, LCA는 right subtree에 위치
        elif p.val > root.val < q.val:
            root = root.right

        # (1), (2)에 해당하지 않으면 현재 root가 LCA
        else:
            return root

Complexity

• Time: O(height)
• Space: O(1)