> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binary_tree_and_divide_conquer/divide-and-concquer/865.-smallest-subtree-with-all-the-deepest-nodes.md).

# 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，否则返回深度更深的子树的结果。

```cpp
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;
    }
};
```