문제 링크

문제 해설

Idea

  • root부터 조건을 만족하는 깊이까지 재귀적으로 자식 노드를 탐색하면서
    p 또는 q 노드를 발견한 경우 해당 노드를 호출한 함수에게 반환
  • 최종적으로 좌,우에 각각 p와 q가 있을 경우 깊이가 가장 깊은 부모 노드를 반환하고,
    한쪽 방향에 p와 q가 몰려있을 경우 둘 중 부모 관계에 있는 노드를 반환

Time Complexity

  • O(N) = 10^5

Data Size

  • nodes: [2, 10^5]
  • val: -10^9 <= int <= 10^9

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

# 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 root:
            if root == p or root == q:
                return root

            left = self.lowestCommonAncestor(root.left, p, q)
            right = self.lowestCommonAncestor(root.right, p, q)

            if left and right:
                return root
            return left if left else right