1#include <utility>
2
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
8};
9
10class Solution {
11public:
12    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
13        return dfs(root).first;
14    }
15    std::pair<TreeNode*, int> dfs(TreeNode* node) {
16        if (!node) return {nullptr, 0};
17        auto left = dfs(node->left);
18        auto right = dfs(node->right);
19        if (left.second > right.second) return {left.first, left.second + 1};
20        if (right.second > left.second) return {right.first, right.second + 1};
21        return {node, left.second + 1};
22    }
23};