题目

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

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

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

Return the node with the largest depth such that it contains all the deepest nodes in its subtree.

Example 1:

Input: [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 colored in blue are the deepest nodes of the tree.
The input "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" is a serialization of the given tree.
The output "[2, 7, 4]" is a serialization of the subtree rooted at the node with value 2.
Both the input and output have TreeNode type.

思路：

包含所有最深叶子结点的最小子树必然包含这样的特点，它的左右子树的高度相同。所以需要使用递归查找最深的深度，然后在进行判断当左右子树的高度相同的时候记录下当前子树的根结点。同时不要忘记更新最深深度。

代码：

int max = 0;
TreeNode res = null;
public TreeNode subtreeWithAllDeepest(TreeNode root) {
    if(root == null){
        return null;
    }
    dfs(root, 0);
    return res;
}
    
private int dfs(TreeNode root, int level){
    if(root == null){
        return level;
    }
    int left = dfs(root.left, level + 1);
    int right = dfs(root.right, level + 1);
    if(left == right && left >= max){
        res = root;
        max = left;
    }
    return Math.max(left, right);
}