[Leetcode/파이썬] 236. Lowest Common Ancestor of a Binary Tree

Product of Array Except Self

---

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

 

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

 

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

 

# 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':
        if not root or root == p or root == q:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if not right :
            return left
        if not left :
            return right
        if left and right :
            return root

p와 q를 동시에 만족하는 부모를 찾는 문제이다. p와 q 중에 하나가 답이 될 수도 있고, 그 위의 노드가 답이 될 수도 있다. 

정답처리 코드를 하나 미리 해놓자. 왜냐하면 루트가 비어있거나, 루트노드가 p나 q일 경우에 바로 정답처리를 해버리고, 혹여나 재귀로 들어갈 경우, left나 right가 된다. 

루트 노드에서 왼쪽으로 가는 left, 오른쪽으로 가는 right 하나씩 찾는다. 이진 트리기 때문에 2개만 세팅해놓고 재귀를 돌자.

left나 right 중에서 만약 값이 존재하지 않으면 둘 중 값이 존재하는 하나를 return, 둘 다 값이 존재하면 root를 리턴.

그 이유는 왼쪽에 p와 q가 둘 다 존재하면 그 중 더 상위 노드가 left에 return 되게 되며, right는 값이 없는 상태로 return 되게 된다. 

동일한 이유로 오른쪽도 마찬가지가 된다. 만약 둘 다 값이 존재하면 root, 가장 위에 있는 노드가 return 되게 된다.