1123. Lowest Common Ancestor of Deepest Leaves (Hash Table, Tree, Depth-First Search, Breadth-First Search, Binary Tree)

링크 - https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/description/?envType=company&envId=facebook&favoriteSlug=facebook-thirty-days

난이도 - Medium

Intuition

우리는 dfs로 이 문제를 풀 수 있다. 먼저 node의 left와 right를 먼저 보는 식으로 dfs를 진행한다. 그리고 반환할때 그때의 깊이 (가장 깊은게 0부터 시작)와 그 노드를 반환한다. 그리고 깊이가 더 깊은 쪽의 노드를 반환하는 식으로 LCA를 반환한다.

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def lcaDeepestLeaves(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node):
            if not node:
                return 0, None

            left = dfs(node.left)
            right = dfs(node.right)

            if left[0] > right[0]:
                return left[0] + 1, left[1]
            if right[0] > left[0]:
                return right[0] + 1, right[1]
            return left[0] + 1, node

        res = dfs(root)
        return res[1]

Complexity

Time Complexity: O(n)

Space Complexity: O(n)