[LeetCode] 235. Lowest Common Ancestor of a Binary Search Tree 풀이 및 코드

문제

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and qas descendants (where we allow a node to be a descendant of itself).”

BST가 주어질 때 가장 낮은 공통의 조상을 찾아라.

---

코드

문제 풀면서 주의 해야 했던 사항은 

1. 모든 노드가 unique 하다는 것 (즉, root <= root.right이 아니라 root < root.right이라는 것!)
2. 자기 자신도 자신의 조상이 될 수 있다는 것

이었다.

(만약에 해당 문제가 코딩 테스트에 나온다면 이 사항에 대해 미리 질문하여 확실히 하고 넘어가야 할 것 같다....)

공통의 조상을 찾는 것이므로 root를 먼저 방문해야 한다고 생각했다. 따라서 순회는 preorder로 진행하였다.

코드를 제출하고 나니 조금더 간추려서 쓸 수도 있을 것 같지만...우선은 이렇게 남겨두겠다...

# 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):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if q.val < p.val:
            p, q = q, p
        
        if root:
            if p.val <= root.val <= q.val:
                return root
            
  
        if root.left:
            res1 = self.lowestCommonAncestor(root.left, p, q)
            if res1:
                return res1
            
        if root.right:
            res2 =self.lowestCommonAncestor(root.right, p, q)
            if res2:
                return res2