Leetcode 1676. Lowest Common Ancestor of a Binary Tree IV

문제

Given the root of a binary tree and an array of TreeNode objects nodes, 
return the lowest common ancestor (LCA) of all the nodes in nodes. 
All the nodes will exist in the tree, and all values of the tree's nodes are unique.

• 이진트리 root와 그 node들의 리스트인 nodes가 주어진다.
• nodes의 가장 레벨이 높은 공통 조상을 찾으시오.

---

예시

root = [3,5,1,6,2,0,8,null,null,7,4], nodes = [4,7]
- 4와 7의 가장 가까운 / 레벨이 높은 공통 조상은 2이다.
답 : 2

---

제한

• 노드의 갯수는 $[1, 10^4]$ 범위 내이다.
• $-10^9 <= Node.val <= 10^9$
• 모든 nodes의 노드는 반드시 이진트리에 포함된다.
• 모든 nodes의 노드는 서로 다르다.

---

풀이

1. root에서 왼쪽과 오른쪽에 각각 node가 포함되는지 확인한다.
2. 만약 한쪽에 포함이 되어 있지 않으면 반대쪽에 전부 있다는 뜻이기에 그것을 리턴한다.
3. 둘다 있으면 root를 리턴한다.

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
        if not root:
            return None
        if root in nodes:
            return root

        left = self.lowestCommonAncestor(root.left, nodes)
        right = self.lowestCommonAncestor(root.right, nodes)

        if not left:
            return right
        if not right:
            return left

        return root