865. Smallest Subtree with all the Deepest Nodes

https://leetcode.com/problems/smallest-subtree-with-all-the-deepest-nodes/

找出所有最深叶子的LCA(lowest common ancestor)。二叉树问题=>分治。直观解法是先统计所有最深叶子的个数cnt，再用一个额外的分治统计左右子树包含了多少最深叶子，当l+r刚好==cnt时该结点即所求。还可以更优化，分治统计左右子树的深度并让左右子树返回它们各自子树的结果，当它俩深度相同时说明cur是当前同时涵盖了最深叶结点的LCA，否则返回深度更深的子树的结果。

class Solution {
public:
    pair<int, TreeNode*> dfs(TreeNode *cur) {
        if (cur == nullptr) return {0, nullptr};
        const auto l = dfs(cur->left), r = dfs(cur->right);
        const auto dl = l.first, dr = r.first;
        return {max(dl, dr) + 1, dl == dr ? cur : dl > dr ? l.second : r.second};
    }

    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        return dfs(root).second;
    }
};