[LeetCode] 236. Lowest Common Ancestor of a Binary Tree

Binary 트리 하나와 해당 트리에 속한 두 개의 노드가 주어진다. 이 때, 두 노드의 공통 조상 중 가장 낮은 Node 즉, Lowest common ancestor 를 찾아라.

 

제약 조건

2 <= node 개수 <= 10^5 

설명: n개의 node가 있으면 O(n)의 시간복잡도를 가짐. 노드의 개수가 10^5까지면 전체 트리를 순회하는 데에 시간초과가 나지 않을 것.(넣었을 때 10^8이 넘지 않기 때문 -> 시간제한 초과하지 않음) 

 

-10^9 <= Node.val <= 10^9 

설명: "-10^9"는 4byte 짜리 int형 자료형에 저장할 수 있다는 뜻 (4byte가 표현할 수 있는 수의 범위: -2^31 ~ 2^31-1)

("-10^9"는 저 범위 안에 포함이 되기 때문에 제한 조건을 줌)

 

모든 Node.val은 unique 하다. (예외사항=중복값 제한)

설명: p != q (p, q는 모두 주어진 Tree 안에 속해 있다.)

 

 

# 가장 낮은 공통 조상의 노드를 반환한다. (왼쪽, 오른쪽에서 정보가 들어오고 그 둘을 취합해서 특정값을 반환해준다.)
def LCA(root, p, q):
    if root == None:
        return None
    left = LCA(root.left, p, q) # 재귀
    right = LCA(root.right, p, q)
    if root == p or root == q:
        return root
    elif left and right:
        return root
    return left or right

# left, right의 정보 먼저 방문하고, 그 결과값을 태도로 다음 노드를 방문 (Postorder와 비슷)
# postorder 방식으로 트리 순회 (left를 방문한 다음 right child 방문. 그 다음 스스로(root)를 방문)

LCA([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4] ,6, 4)

 

 

 

 

 

 

 

 

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

Lowest Common Ancestor of a Binary Tree - LeetCode