865.具有所有最深节点的最小子树

链接：865.具有所有最深节点的最小子树
难度：Medium
标签：树、深度优先搜索、广度优先搜索、哈希表、二叉树
简介：给定一个根为 root 的二叉树，每个节点的深度是 该节点到根的最短距离 。返回包含原始树中所有 最深节点 的 最小子树 。

题解 1 - cpp

• 编辑时间：2023-09-06
• 执行用时：8ms
• 内存消耗：13.76MB
• 编程语言：cpp
• 解法介绍：dfs。

class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        function<pair<int, TreeNode*>(TreeNode*, int)> dfs = [&](TreeNode *node, int level) -> pair<int, TreeNode*> {
            pair<int, TreeNode*> res = make_pair(level, node);
            if (node->left) {
                res = dfs(node->left, level + 1);
            }
            if (node->right) {
                auto rres = dfs(node->right, level + 1);
                if (rres.first > res.first) res = rres;
                else if (rres.first == res.first) res.second = node;
            }
            return res;
        };
        return dfs(root, 0).second;
    }
};