Leetcode 865. Smallest Subtree with all the Deepest Nodes

문제

Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

• 주어진 이진트리에 대해 가장 깊이가 큰 노드들을 모두 자식으로 가지는 가장 큰 깊이의 노드를 구하시오

예시

• 7과 4가 가장 깊은 노드이고 두 노드를 자식으로 가지는 노드는 2이다.
• 정답은 2 노드

제한

• 전체 노드의 갯수와 값 둘다 1~500 사이이다.
• 트리 내 노드의 값은 유니크하다.

풀이

class Solution:
    def subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        def dfs(node: Optional[TreeNode]):
            if not node:
                return None, 0

            left_node, left_depth = dfs(node.left)
            right_node, right_depth = dfs(node.right)

            if left_depth > right_depth:
                return left_node, left_depth + 1
            elif left_depth < right_depth:
                return right_node, right_depth + 1
            else:
                return node, left_depth + 1

        return dfs(root)[0]

• 왼쪽 노드가 깊다 -> 왼쪽 노드에 몰려 있기에 그걸 리턴
• 오른쪽 노드가 깊다 -> 오른쪽 노드에 몰려 있기에 그걸 리턴
• 두 노드가 같다 -> 본 노드가 정답