2026-01-09 11:15:58 +0300 MSK

# 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 subtreeWithAllDeepest(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        neg_inf = float("-inf")

        def dfs(node: TreeNode, depth: int) -> tuple[TreeNode, int]:
            if node.left is None and node.right is None:
                return node, depth
            if node.left is None:
                return dfs(node.right, depth + 1)
            if node.right is None:
                return dfs(node.left, depth + 1)
            left_node, left_depth = dfs(node.left, depth + 1)
            right_node, right_depth = dfs(node.right, depth + 1)
            if left_depth == right_depth:
                return node, left_depth
            if left_depth > right_depth:
                return left_node, left_depth
            return right_node, right_depth
        
        return dfs(root, 0)[0]