题目描述

给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。

如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是 最深的。

一个结点的子树是该结点加上它的所有后代的集合。

返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。

样例

输入：[3,5,1,6,2,0,8,null,null,7,4]
输出：[2,7,4]
解释：
我们返回值为 2 的结点，在图中用黄色标记。
在图中用蓝色标记的是树的最深的结点。
输入 "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" 是对给定的树的序列化表述。
输出 "[2, 7, 4]" 是对根结点的值为 2 的子树的序列化表述。
输入和输出都具有 TreeNode 类型。

![](https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/01/sketch1.png输出：[2,7,4]

注意

• 树中结点的数量介于 1 和 500 之间。
• 每个结点的值都是独一无二的。

算法

(宽度优先遍历，BFS) $O(n)$

1. 通过 BFS 求出每个结点的深度，并且将结点分层存放在数组中。
2. 将叶结点标记为 true，如果仅有一个叶结点，则直接返回这个叶结点。
3. 否则，按层数从深到浅遍历，如果当前层的某个结点的左儿子或右儿子被标记了，则自己也被标记。如果当前层仅有一个被标记的结点，则返回该结点。否则继续上一层。

时间复杂度

• 每个结点仅被遍历常数次，故时间复杂度为 $O(n)$。

空间复杂度

• 需要队列和分层数组的空间，以及存放深度，标记的哈希表，总空间复杂度为 $O(n)$。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* subtreeWithAllDeepest(TreeNode* root) {
        unordered_map<TreeNode*, int> depth;
        unordered_map<TreeNode*, bool> leaf;
        vector<vector<TreeNode*>> level;
        int max_depth = 0;

        queue<TreeNode*> q;
        q.push(root);
        depth[root] = 1;

        while (!q.empty()) {
            TreeNode *sta = q.front();
            q.pop();
            max_depth = max(max_depth, depth[sta]);

            if (level.size() < depth[sta])
                level.emplace_back(vector<TreeNode*>());

            level[depth[sta] - 1].push_back(sta);

            if (sta -> left != nullptr) {
                depth[sta -> left] = depth[sta] + 1;
                q.push(sta -> left);
            }
            if (sta -> right) {
                depth[sta -> right] = depth[sta] + 1;
                q.push(sta -> right);
            }
        }

        int counter = 0;
        TreeNode *ans;

        for (auto &t : level[max_depth - 1]) {
            leaf[t] = true;
            counter++;
            ans = t;
        }

        if (counter == 1)
            return ans;

        for (int i = max_depth - 2; i >= 0; i--) {
            counter = 0;
            for (auto &t : level[i])
                if (leaf[t -> left] || leaf[t -> right]) {
                    leaf[t] = true;
                    counter++;
                    ans = t;
                }

            if (counter == 1)
                break;
        }
        return ans;
    }
};