leetcode easy : Lowest Common Ancestor of a Binary Search Tree

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

Lowest Common Ancestor of a Binary Search Tree - LeetCode

 

BST가 주어지고 노드 p와 q가 주어질때 두 노드의 common ancestor 노드를 찾는 문제다. common ancestor 중에 가장 낮은걸 찾아야한다.

BST이므로 값을 조사하면 특정 노드가 lowest common ancestor인지 아닌지 알수있다. 특정 노드 기준으로 p와 q의 값이 모두 노드값보다 작으면 왼쪽 subtree에 p와 q가 모두 속해있다는 뜻일거니까 그 '특정노드'는 'lowest' common ancestor는 아닐것이다. p와 q값이 모두 노드값보다 큰 경우도 common ancestor일수는 있어도 'lowest'는 아닐것이다.

 

아래는 다른 사람의 솔루션이다.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        while (root.val - p.val) * (root.val - q.val) > 0:
            root = (root.left, root.right)[p.val > root.val]
        return root