Given the root of a binary tree, the depth of each node is the shortest distance to the root.

Return the smallest subtree such that it contains all the deepest nodes in the original tree.

A node is called the deepest if it has the largest depth possible among any node in the entire tree.

The subtree of a node is a tree consisting of that node, plus the set of all descendants of that node.

&nbsp;
Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4]
Output: [2,7,4]
Explanation: We return the node with value 2, colored in yellow in the diagram.
The nodes coloured in blue are the deepest nodes of the tree.
Notice that nodes 5, 3 and 2 contain the deepest nodes in the tree but node 2 is the smallest subtree among them, so we return it.


Example 2:

Input: root = [1]
Output: [1]
Explanation: The root is the deepest node in the tree.


Example 3:

Input: root = [0,1,3,null,2]
Output: [2]
Explanation: The deepest node in the tree is 2, the valid subtrees are the subtrees of nodes 2, 1 and 0 but the subtree of node 2 is the smallest.


&nbsp;
Constraints:


	The number of nodes in the tree will be in the range [1, 500].
	0 &lt;= Node.val &lt;= 500
	The values of the nodes in the tree are unique.


&nbsp;
Note: This question is the same as 1123: https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves/

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:

        # find a set of deepest nodes first
        deepest_nodes = [0]
        self.find_deepest(root, 0, deepest_nodes)
        
        # extract the depth and also make a set out of the values
        targets = set(deepest_nodes[1:])

        # get the subtree
        return self.find_merge(root, targets)[0]

    def find_deepest(self, node, current_depth, deepest_nodes):

        # make a check
        if not node:
            return
        
        # make a check if we are a deep node
        if current_depth > deepest_nodes[0]:
            deepest_nodes.clear()
            deepest_nodes.append(current_depth)
            deepest_nodes.append(node.val)
        elif current_depth == deepest_nodes[0]:
            deepest_nodes.append(node.val)
        
        # go deeper
        self.find_deepest(node.left, current_depth+1, deepest_nodes)
        self.find_deepest(node.right, current_depth+1, deepest_nodes)
    
    def find_merge(self, node, targets):

        # make a check
        if not node:
            return None, set()

        # check whether we are a target
        found = set()
        if node.val in targets:
            found.add(node.val)

        # go deeper and get result nodes
        nleft, left = self.find_merge(node.left, targets)
        if nleft is not None:
            return nleft, set()
        nright, right = self.find_merge(node.right, targets)
        if nright is not None:
            return nright, set()

        # merge the found set
        found = found | left | right

        # check whether we found all
        if not (targets - found):
            return node, set()
        else:
            return None, found
class Solution {
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
		if (root.left == null && root.right == null) return root;
        int depth = findDepth(root);
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int count = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            count++;
            if (count == depth) {
                break;
            }
            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                if (cur.left != null) q.offer(cur.left);
                if (cur.right != null) q.offer(cur.right);
            }
        }
        Set<Integer> set = new HashSet<>();
        while (!q.isEmpty()) {
            set.add(q.poll().val);
        }
        return find(root, set);
    }
    
    public int findDepth(TreeNode root) {
        if (root == null) return 0;
        int left = findDepth(root.left);
        int right = findDepth(root.right);
        return 1 + Math.max(left, right);
    }
    
    public TreeNode find(TreeNode root, Set<Integer> set) {
        if (root == null) return root;
        if (set.contains(root.val)) return root;
        TreeNode left = find(root.left, set);
        TreeNode right = find(root.right, set);
        if (left != null && right != null) return root;
        else if (left != null) return left;
        else if (right != null) return right;
        else return null;
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void help(TreeNode* root, TreeNode* par, map<TreeNode*,TreeNode*> &m)
    {
        if(root==NULL)
            return;
        m[root]=par;
        help(root->left,root,m);
        help(root->right,root,m);
    }
    TreeNode* subtreeWithAllDeepest(TreeNode* root) 
    {
        TreeNode* r=root;
        map<TreeNode*,TreeNode*>m;
        help(r,NULL,m);
        queue<TreeNode*>q;
        vector<TreeNode*>ans;
        q.push(root);  
        while(!q.empty())
        {
            int s=q.size();
            vector<TreeNode*>a;
            for(int i=0;i<s;i++)
            {
                TreeNode* bgn=q.front();
                q.pop();
                a.push_back(bgn);
                if(bgn->left!=NULL)
                    q.push(bgn->left);
                if(bgn->right!=NULL)
                    q.push(bgn->right);
            }
            ans=a;
        }
        if(ans.size()==1)
            return ans[0];
        set<TreeNode*>s;
        while(s.size()!=1)
        {
            s.clear();
            for(int i=0;i<ans.size();i++)
            {
                ans[i]=m[ans[i]];
            }
            s.insert(ans.begin(),ans.end());
        }
        for(auto i : s)
        {
            return i;
        }
        return NULL;
    }
};
var subtreeWithAllDeepest = function(root) {
    // keep track of deepest till now
    // if left right has both deepest than it will be the ans;
    let mx = 0, rm = 0, ans = null;
    const compute = (r = root, d = 0) => {
        if(!r) {
            rm = Math.max(rm, d);
            return d;
        }
        const ld = compute(r.left, d + 1);
        const rd = compute(r.right, d + 1);
        
        if(ld == rd && ld == mx) {
            ans = r;
        }
        if(mx < rm) {
            ans = r;
            mx = rm;
        }
        
        return Math.max(ld, rd);
    }
    compute();
    return ans;
};
Smallest Subtree with all the Deepest Nodes