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

235. Lowest Common Ancestor of a Binary Search Tree

Easy

Given a binary search tree (BST), find the lowest common ancestor (LCA) node 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 q as descendants (where we allow a node to be a descendant of itself).”

 

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1
Output: 2

 

Constraints:

• The number of nodes in the tree is in the range [2, 105].
• -109 <= Node.val <= 109
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

---

문제 풀이

문제 접근

1. 바이너리 트리 문제로 p, q의 공통 부모를 찾자.
2. 제한 조건을 봤을때, 갯수가 많지 않기 때문에 재귀 탐색으로 풀 수 있을 것 같다.

풀이

1. 공통 분모가 찾아지는 방식은 두가지 케이스가 있다.
2. 왼쪽 서브트리와 오른쪽 서브트리에 존재한다.
3. 현재 노드와 왼쪽 서브트리 혹은 오른쪽 서브트리에 존재한다.
4. 이 두가지를 모두 만족 시키기위해서는 노드를 찾았을때 탐색을 끝내면 안된다.
5. 탐색이 끝나는건 모든 자식 노드를 탐색하고 돌아올때 노드가 존재햇을 때이다. 
6. 즉, Post-Order 방식으로 트리를 순회 하면서 두가지 케이스를 처리해준다.
7. 현재 노드가 p, q 노드 중 하나와 같을때 자식 서브트리 결과중 True가 있다면 정답을 저장한다.
8. 그리고 True를 리턴하고 만일 왼쪽, 오른쪽 서브트리 반환 값이 모두 True 이면 정답을 저장한다.
9. 마지막으로 반환을 하고 종료할때는 왼쪽, 오른쪽 서브트리의 반환 값을 or 연산하여 반환한다. 
   *(둘 중 하나라도 True 라면 부모노드를 최상 노드로 하는 서브트리는 항상 True 이기 때문이다.

소스 코드

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

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        self.res = None
        def rec(node, p, q):
            if not node:
                return False
            l = rec(node.left, p, q)
            r = rec(node.right, p, q)
            if node == p or node == q:
                if l or r:
                    self.res = node
                return True
            elif l and r:
                self.res = node
            return l or r
        rec(root, p, q)
        return self.res