死了么APP爆火，下载量冲到付费榜第一，开发者是3个95后。

1月10日，一款名为“死了么”的APP突然走红网络，并且该APP下载量一度冲到苹果工具类付费榜榜首。该app专门为独居人群打造，尤其是独居老人，在该app中设置紧急联系人和邮箱，如果用户连续多日没有在该app内签到，则系统将于次日主动发送邮件告诉紧急联系人。

也有网友认为“死了么”名字不吉利，建议改名为“活着吗”。该团队只有3个人，都是95后，该软件爆火之后，已实现盈利，APP最初定价为1元，近期已调整为8元，他们计划以100万出让10%的股份。

还有很多网友说这APP没啥难度，很容易被模仿。并且每天都要打开签到，比较麻烦，如果忘记了就会发送邮件给积极联系人。实际上很多大型的app都可以做，随便举个例子，比如有些人爱看抖音，抖音APP只需要监听他今天有没有打开抖音即可，如果没有打开就发邮件给紧急联系人，这样不需要签到，还不容易出现忘记的情况。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第865题：具有所有最深节点的最小子树，难度是中等。

给定一个根为 root 的二叉树，每个节点的深度是该节点到根的最短距离 。返回包含原始树中所有最深节点的最小子树 。如果一个节点在整个树的任意节点之间具有最大的深度，则该节点是最深的 。一个节点的子树是该节点加上它的所有后代的集合。

示例1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4] 输出：[2,7,4] 解释： 我们返回值为 2 的节点，在图中用黄色标记。 在图中用蓝色标记的是树的最深的节点。 注意，节点 5、3 和 2 包含树中最深的节点，但节点 2 的子树最小，因此我们返回它。

• 树中节点的数量在 [1, 500] 范围内。

• 0 <= Node.val <= 500

• 每个节点的值都是独一无二的。

问题分析

这题说的是返回一个最小的子树，并且原来二叉树中所有的最深节点都在这棵子树中，如果我们换个思路，这题实际上是求所有最深节点的最近公共祖先。

我们可以使用自下而上的方式来遍历这棵二叉树，返回的有两个值，一个是该节点的深度，另一个是该节点下包含所有最深节点的最小子树。

1，如果左右子树一样深，说明左右子树都有最深节点，需要返回当前节点。

2，如果左子树最深，说明最深节点在左子树上，返回左子树的结果即可。

3，如果右子树最深，说明最深节点在右子树上，返回右子树的结果即可。

JAVA：

public TreeNode subtreeWithAllDeepest(TreeNode root){
    return dfs(root).getValue();
}


 // key是节点的高度
private Pair 
 
   
 dfs(TreeNode root){
    if (root == null)
        return new Pair<>(0, null);
    // 递归左右子树
    Pair 
 
 left = dfs(root.left), right = dfs(root.right); 
 
    if (left.getKey().intValue() == right.getKey())//  左右子树一样深
        return new Pair<>(left.getKey() + 1, root);
    if (left.getKey() > right.getKey())//  左子树更深
        return new Pair<>(left.getKey() + 1, left.getValue());
    return new Pair<>(right.getKey() + 1, right.getValue());//  右子树更深
}

C++：

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


     // key是节点的高度
    pair dfs(TreeNode *root){
        if (root == nullptr)
            return {0, nullptr};
        // 递归左右子树
        auto left = dfs(root->left), right = dfs(root->right);
        if (left.first == right.first)//  左右子树一样深
            return {left.first + 1, root};
        if (left.first > right.first)//  左子树更深
            return {left.first + 1, left.second};
        return {right.first + 1, right.second};//  右子树更深
    }

笔者简介

博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解900多题，对算法题有自己独特的解题思路和解题技巧。